使用卡特蘭數來解決的問題
使用卡特蘭數來解決的問題
作者：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的數量
