题目要求
P1044题目链接
题意就是:N个数依次进栈,可随机出栈,算一下可能的出栈序列数。
其实这个就是Catalan啊,如果数据结构与算法有一定的刷题积累的学生应该经常做这样的About栈的题:
- 下列出栈序列中可能的是()
- 下列出栈序列中不可能的是()
- 出栈的可能序列数是多少?
前两种你可以自己推一推,最后一种总不能乱猜吧? 而结论正是来源于此呢。
我比较菜,就学了大佬的Catalan解法做的题并简单写写题解。
建立int类型数组catalan。 catalan[i]表示i个数出栈的全部可能数。 先初始化两个值:catalan[0] = 1, catalan[1] = 1。 这是显然的,不解释。
设x为当前出栈序列的最后一个,则x有n种取值。
而由于x是最后一个出栈的,所以可以将已经出栈的数分成两部分:
- 比x小
- 比x大
比x小的数有x-1个,所以这些数的全部出栈可能为catalan[x-1]; 比x大的数有N-x个,所以这些数的全部出栈可能为catalan[n-x]。
这两部分互相影响,所以一个x的取值能够得到的所有可能性为catalan[x-1] * catalan[n-x]
另外,由于x有n个取值,所以得到最终的式子:
catalan[n] = f[0] * f[n-1] + f[1] * f[n-2] + … + f[n-1] * f[0]
下面是核心算法的Java实现代码:
catalan[0] = 1;
catalan[1] = 1;
for (int i = 2; i
关注
打赏
热门博文
- 【Linux】Ubuntu20.04安装和卸载MySQL8
- 【Linux】Ubuntu 20.04 报错 curl: (23) Failure writing output to destination 的解决方法
- 【Java】JUnit 4.13.2 警告 ‘assertEquals(double, double)‘ is deprecated 的解决方法
- 【JavaScript】处理 @parcel/transformer-js: Browser scripts cannot have imports or exports.
- 【Node.js】Windows环境安装配置NVM和Node.js
- 【Python】处理TypeError: Plain typing.NoReturn is not valid as type argument
- 【Python】Matplotlib可视化50例
- 【C语言】C语言修改MySQL数据库
- 【Java】从默认包导入类和对象报错的解决方法
- 【Java】panel.getGraphics()报错空指针异常的解决方法