使用卡特兰数来解决的问题
使用卡特兰数来解决的问题
作者：Grey
原文地址：
通项公式
k(0) = 1, k(1) = 1，如果接下来的项满足：
k(n) = k(0) x k(n - 1) + k(1) x k(n - 2) + …… + k(n - 2) x k(1) + k(n - 1) x k(0)
或者
k(n) = C(2n, n) - C(2n, n-1)
或者
k(n) = C(2n, n) / (n + 1)
就说这个表达式，满足卡特兰数。
比如
n 个左括号，n 个右括号，有多少种合法的组合方式？合法的定义是任何一个前缀串，右括号的数量必须小于左括号的数量。
合法的不好求，我们可以先求不合法的，因为总的方法数是C(2n,n)（先安排 n 个左括号，另外的位置自然成为右括号的位置）
不合法的情况是：一定存在一个前缀，右括号的数量 = 左括号的数量 + 1，即不合法的数量等于C(2n, n+1),
所以合法的数量等于C(2n,n) - C(2n,n+1)，即C(2n,n) - C(2n,n-1)。
满足卡特兰数。
再如
给定 n 个数字，且每个数字都必须入栈，也必须出栈，求这些数合法的出栈入栈的顺序有多少种？
由于每个数字有出栈和入栈两个操作，所以，一共的操作组合有（包括不合法的方式）C(2n,n),
由于出栈的次数一定不可能大于入栈的次数，所以，不合法的组合方式中：一定存在一个出入栈的方式，出栈的次数 = 入栈次数 + 1，即C(2n, n + 1)，合法的出入栈次数是C(2n,n) - C(2n, n + 1)，即C(2n, n) - C(2n, n - 1)，满足卡特兰数。
类似的还有
曲线在第一象限，可上升，可下降，求有多少种组合方式？
也满足卡特兰数。
N个节点有多少种形态的二叉树
有N个二叉树节点，每个节点彼此之间无任何差别，返回由N个二叉树节点，组成的不同结构数量是多少？
题目链接：
LintCode 163 · Unique Binary Search Trees
LeetCode 96. Unique Binary Search Trees
主要思路
有 0 个节点的时候，只有 1 种方法，即空树
有 1 个节点的时候，只有 1 种方法，即只有一个节点的树
有 2 个节点的时候，有 2 种方法，分别是
即: k(0) = 1, k(1) = 1, k(2) = 2
当数量为 n 时，有如下一些情况，根节点占一个节点，然后
左树 0 个节点 ，右数 n – 1 个节点；
左树 1 个节点，右数 n – 2 个节点；
左树 2 个节点，右数 n – 3 个节点；
……
左树 n – 1 个节点 ，右数 0 个节点；
左树 n – 2 个节点，右数 1 个节点；
左树 n – 3 个节点，右数 2 个节点；
即：k(n) = k(0) x k(n - 1) + k(1) x k(n - 2) + …… + k(n - 2) x k(1) + k(n - 1) x k(0)，满足卡特兰数。
完整代码如下
import java.math.BigInteger;
public class Solution {
/**
* @param n: An integer
* @return: An integer
*/
public static int numTrees(int n) {
if (n < 0) {
return BigInteger.ZERO.intValue();
}
if (n < 2) {
return BigInteger.ONE.intValue();
}
BigInteger a = BigInteger.ONE;
BigInteger b = BigInteger.ONE;
for (int i = 1, j = n + 1; i <= n; i++, j++) {
a = a.multiply(BigInteger.valueOf(i));
b = b.multiply(BigInteger.valueOf(j));
BigInteger gcd = gcd(a, b);
a = a.divide(gcd);
b = b.divide(gcd);
}
return (b.divide(a)).divide(BigInteger.valueOf(n + 1)).intValue();
}
public static BigInteger gcd(BigInteger m, BigInteger n) {
return n.equals(BigInteger.ZERO) ? m : gcd(n, m.mod(n));
}
private static int numTrees2(int n) {
if (n < 0) {
return BigInteger.ZERO.intValue();
}
if (n < 2) {
return BigInteger.ONE.intValue();
}
BigInteger a = BigInteger.valueOf(n + 1);
BigInteger b = BigInteger.valueOf(1);
for (int i = n + 2; i <= (2 * n); i++) {
a = a.multiply(BigInteger.valueOf(i));
}
for (int i = 1; i <= n; i++) {
b = b.multiply(BigInteger.valueOf(i));
}
return a.divide(b).divide(BigInteger.valueOf(n + 1)).intValue();
}
}
1 0 前缀串数量问题
假设给你 n 个 0 和 n 个 1，你必须用全部数字拼序列,返回有多少个序列满足：任何前缀串，1 的数量都不少于 0 的数量
n 个 1 和 n 个 0，所有的排列组合是C(2n,n)，由于合法数量 = 所有组合 - 非法数量，即
C(2n,n) - C(2n,n-1)
完整代码如下
package snippet;
import java.util.*;
//假设给你N个0，和N个1，你必须用全部数字拼序列
// 返回有多少个序列满足：任何前缀串，1的数量都不少于0的数量
// 卡特兰数
public class Code_10Ways {
public static long ways2(int N) {
if (N < 0) {
return 0;
}
if (N < 2) {
return 1;
}
long a = 1;
long b = 1;
long limit = N << 1;
for (long i = 1; i <= limit; i++) {
if (i <= N) {
a *= i;
} else {
b *= i;
}
}
return (b / a) / (N + 1);
}
}
类似的问题
偶数（2N）个人排队，排两行，任何一个排在后面的人都不能比排在前面的人小，有几种排列方式？
其本质就是：前面N个人编号成0，后面N个人编号成1，任何前缀串，1的数量不小于0的数量
