目录

卡塔兰数

题记

卡特兰数(Catalan number)是组合数学中一个常出现在各种计数问题中的数列

卡塔兰数算是leetcode里面的高频题目了,这里就来解决一下卡塔兰数问题。

卡塔兰数

卡塔兰数的一般式是: image-20200924113030793

卡塔兰数的等价式为: image-20200924113055452

卡塔兰数的题目

96 不同的二叉搜索树

给定一个整数 n,求以 1 … n 为节点组成的二叉搜索树有多少种?

这道题的动态规划解法我已经在这篇博客里面介绍过了。

解题思路

可组成的数量就是左子树可组成的数量乘以右子树可组成的数量。

比如[1,2,3,4]:

对1当根节点,则有dp[0]*dp[3],左子树为null,右子树为[2,3,4]

对2当根节点,则有dp[1]*dp[2],左子树为[1],右子树为[3,4]

对3当根节点,则有dp[2]*dp[1],左子树为[1,2],右子树为[4]

对4当根节点,则有dp[3]*dp[0],左子树为[1,2,3],右子树为null

即$dp[n] = \sum_{i=0}^{n-1}dp[i]*dp[n-i-1]$

上式满足卡塔兰数的第二个等价式,可以替换成第三个等价式,从而得到空间复杂度O(1),时间复杂度O(n)的代码。

代码

1
2
3
4
5
6
class Solution(object):
    def numTrees(self, n):
        C = 1
        for i in range(0, n):
            C = C * 2*(2*i+1)/(i+2)
        return int(C)

同样可以写出卡塔兰数一般式$\frac{1}{n+1}C_{2 n}^{n}$的代码,不过力扣提交结果的执行耗时上上面的代码更好;而acwing 130由于测试用例的n值很大,只有下面使用math库的代码通过了,其他2个都超时了。

使用math库:

1
2
3
4
5
6
import math
class Solution:
    def numTrees(self, n):
        A = math.factorial(2*n)
        B = math.factorial(n)
        return A//B//B//(n+1)

不使用math库(这个代码是三个里面最不推荐的):

1
2
3
4
5
6
7
8
9
class Solution:
    def numTrees(self, n):
        C = 1
        # print(A//B)
        for i in range(n+1,2*n+1):
            C*=i
        for i in range(1,n+1):
            C=C//i # 这里一定要是整除,不然有精度问题
        return C//(n+1)

进出栈序列

n 个元素进栈序列为:1,2,3,4,...,n,则有多少种出栈序列。

frame_00003.png

上图所示是一种出栈序列,可以用[+1, -1, +1, +1, -1, -1]来表示 。

所有的-1,+1的排列组合有$C_{2n}^n$个,因为相当于有2n个位置,放n个+1(剩下的位置都是-1)。

但是因为-1之前一定要有足够的+1,如[+1, -1, -1, +1]是不合法的,所以要减去不合法的数量。

观察不合法的序列[+1, -1, -1, +1],不合法的位置是第3个-1,将前3项取反,得到[-1, +1, +1, +1]。取反后是1个-1和3个+1。

不合法序列总是出现在第2m+1(1、3、5….)处有一个-1,且前2m个数值为m个+1 和 m个-1,后2n-(2m+1)个数里面有n-m个+1 和 n-m-1个-1。

将前2m+1个数取反: 前2m个数字中有m个+1 和 m个-1,第2m+1个数是+1,后2n-(2m+1)个数字中有n-m个+1 和 n-m-1个-1,

n+1个+1 和 n-1个-1的序列共有$C_{2n}^{n+1}$种。

不合法的序列和n+1个+1、n-1个-1序列是一一对应的关系,所以不合法序列的数量为$C_{2n}^{n+1}$。

n=4的不合法序列有:

m=1

[-1, -1, +1, +1] -> [+1, -1, +1, +1]

[-1, +1, -1, +1] -> [+1, +1, -1, +1]

[-1, +1, +1, -1] -> [+1, +1, +1, -1]

m=3

[+1, -1, -1, +1] -> [-1, +1, +1, +1]

最终结果为$C_{2n}^n - C_{2n}^{n+1}$,也就是第一个等价式。

非降路径(另一种解释方法)

画一个nxn的格子,从左下角出发,+1表示向右走一格,-1表示向上走一个,走到右上角为有一个序列。

而不合法的序列就是会走到超过对角线虚线的序列。

下图为n=4的可行走法:

image-20200928163509269

可以发现从左下角走到右上角的步数是一定的,即向右走n步、并向上走n步。转化成排列组合,一共2n步,有n个向右走,剩下的都是向上走,一共有$C_{2n}^n$种走法。

而非法路径的特点是,一定会走到y>=x+1的地方。

如下图所示,到绿色的点(n,n)的蓝线是一条非法路径,其与y=x+1的交点用蓝圈标出,将其后半段作y=x+1的对称,此时得到一条从左下角到蓝色的点(n-1,n+1)的路径。

每一条非法路径作对称操作,都能得到这样的一条路径,到点(n-1, n+1)的路径一共有$C_{2n}^{n+1}$个。

p.s. $C_{2n}^{n+1}$是怎么得到的:一共2n(n-1 + n+1)步,有n+1个向上走,剩下的都是向右走。

img

括号序列

n 对括号,则有多少种 “括号匹配” 的括号序列

这题和进出栈序列完全一致,左括号是+1,右括号是-1。

相同的问题还有火车进出栈问题(这是acwing的第130题一列火车n节车厢,依次编号为1,2,3,…,n。每节车厢有两种运动方式,进栈与出栈,问n节车厢出栈的可能排列方式有多少种。acwing的测试样例的n值很大,有个测试用例n是15000,结果手写的阶乘超时了,手写阶乘运算会有精度问题,python用个math库可以解决精度问题,C的话要用质因数分解解决精度问题

买票找零

《编程之美》4.3买票找零:2n个人排队买票,其中n个人持50元,n个人持100元。每张票50元,且一人只买一张票。初始时售票处没有零钱找零。请问这2n个人一共有多少种排队顺序,不至于使售票处找不开钱?

50相当于进栈、100相当于出栈。

证明

递推式推通项式:https://zhuanlan.zhihu.com/p/56821103 感觉这个证明还是挺难的。

除递推式以外的证明:链接 这个相对来说就简单多了

image-20200928210229632

参考资料