使用卡特蘭數來解決的問題

作者：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的數量

演演算法和資料結構筆記

參考資料

演演算法和資料結構體系班-左程雲

使用卡特蘭數來解決的問題

使用卡特蘭數來解決的問題

通項公式

N個節點有多少種形態的二元樹

1 0 字首串數量問題

更多

參考資料