出栈方式

问题等价于可以取出栈顶元素或者栈顶第二个元素 共有多少个出栈序列 这里认为栈内元素没有重复 记dp[i]为有i个元素的栈的出栈序列数 则dp[1] = 1 dp[i]=dp[i-1]+dp[i-1]（对应两种出栈方式） 所以dp[i]=2^(i-1)

能不能这么想，栈里有n个元素，出栈方式的数目记为f(n)，第一次出栈有两种方式：一是出一个元素，此时出栈方式的数目等于剩下n-1个元素的出栈方式数，即f(n-1)；二是出两个元素，这个时候可以选择不入栈和任选一个元素入栈，任选一个元素入栈时为f(n-1)，不入栈时为f(n-2)，所以最终的f(n) = 2f(n-1)+f(n-2).

作者：璐璐 链接：https://www.nowcoder.com/discuss/67377 标题 : 2018秋招阿里巴巴java笔试试题 来源：牛客网 4、堆栈中有元素abcdef，每次出栈可以选择一个或者两个元素栈，当有两个元素出栈时可以选择其中一个重新入栈，则所有元素为空，那么可能的出栈方式有（ ）种？ A.23 B.22 C.21 D.20 E.19 F.18 参考答案：C

import random sum = set() for i in range(0,20000): stack = [] for i in range(1,7): stack.append(i) order = [] while stack: # print(stack) x = stack.pop(-1) order.append(x) if len(stack)>0: if random.randint(0,1) == 1: y = stack.pop(-1) order.append(y) t = random.randint(0,2) if t == 0: stack.append(x) if t == 1: stack.append(y) order = order[::-1] res = [] for i in order: if i not in res: res.append(i) num = 0 for i in res: num = 10*num + i sum.add(int(str(num)[::-1])) sum = (list(sum)) sum.sort(reverse=True) print(sum) print(len(sum))我甚至暴力（相当暴力）搜索了一遍结果是[654321, 654312, 654231, 654213, 653421, 653412, 653241, 653214, 645321, 645312, 645231, 645213, 643521, 643512, 643251, 643215, 564321, 564312, 564231, 564213, 563421, 563412, 563241, 563214, 546321, 546312, 546231, 546213, 543621, 543612, 543261, 543216]32

 同问这个问题，感觉是32

2^5

有81这个答案吗？

求题解

卡特兰数 C(2n,n)-C(2n,n-1)