卡特兰数
- 卡特兰数
- 习题1 假设给你N个0，和N个1，你必须用全部数字拼序列 返回有多少个序列满足：任何前缀串，1的数量都不少于0的数量
- 习题2 有N个二叉树节点，每个节点彼此之间无任何差别 返回由N个二叉树节点，组成的不同结构数量是多少？
- 卡特兰数的算法原型在做题时怎么发现？
卡特兰数
卡特兰数又称卡塔兰数，英文名Catalan number，是组合数学中一个常出现在各种计数问题中出现的数列。其前几项为：
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, …
k(0) = 1, k(1) = 1时，如果接下来的项满足：
k(n) = k(0) * k(n - 1) + k(1) * k(n - 2) + … + k(n - 2) * k(1) + k(n - 1) * k(0)
或者
k(n) = c(2n, n) - c(2n, n-1)
或者
k(n) = c(2n, n) / (n + 1)
就说这个表达式，满足卡特兰数，常用的是范式1和2，3几乎不会使用到
习题1 假设给你N个0，和N个1，你必须用全部数字拼序列 返回有多少个序列满足：任何前缀串，1的数量都不少于0的数量
习题2 有N个二叉树节点，每个节点彼此之间无任何差别 返回由N个二叉树节点，组成的不同结构数量是多少？
卡特兰数的算法原型在做题时怎么发现？
1）如果像题目一一样，这个太明显了，你一定能发现
2）看看题目是不是类题目二问题，比如：
人员站队问题
出栈入栈问题
