*連載轉貼自 http://gpww.blog.163.com ，如圖片顯示有問題，請到原帖...

問題

《編程之美》中提到了“買票找零”問題，查閱了下資料，此問題和卡特蘭數 Cn有關，其定義如下：

卡特蘭數真是一個神奇的數字，很多組合問題的數量都和它有關系，例如：

• Cn= 長度為 2n的 Dyck words的數量。 Dyck words是由 n個 X和 n個 Y組成的字符串，并且從左往右數， Y的數量不超過 X，例如長度為 6的 Dyck words為：

XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY

• Cn= n對括號正確匹配組成的字符串數，例如 3對括號能夠組成：

((())) ()(()) ()()() (())() (()())

• Cn= n+1個數相乘，所有的括號方案數。例如， 4個數相乘的括號方案為：

((ab)c)d (a(bc))d (ab)(cd) a((bc)d) a(b(cd))

• Cn= 擁有 n+1 個葉子節點的二叉樹的數量。例如 4個葉子節點的所有二叉樹形態：

• Cn=n*n的方格地圖中，從一個角到另外一個角，不跨越對角線的路徑數，例如， 4×4方格地圖中的路徑有：

• Cn= n+2條邊的多邊形，能被分割成三角形的方案數，例如 6邊型的分割方案有：

• Cn= 圓桌周圍有 2n個人，他們兩兩握手，但沒有交叉的方案數。

在《Enumerative Combinatorics》一書中，竟然提到了多達 66種組合問題和卡特蘭數有關。

分析

“卡特蘭數”除了可以使用公式計算，也可以采用“分級排列法”來求解。以 n對括弧的合法匹配為例，對于一個序列 (()而言，有兩個左括弧，和一個右括弧，可以看成“抵消了一對括弧，還剩下一個左括弧等待抵消”，那么說明還可以在末尾增加一個右括弧，或者一個左括弧，沒有左括弧剩余的時候，不能添加右括弧。
由此，問題可以理解為，總共 2n個括弧，求 1～2n級的情況，第 i 級保存所有剩余 i 個左括號的排列方案數。 1～8級的計算過程如下表：

計算過程解釋如下： 1級:只能放 1個“(”； 2級:可以在一級末尾增加一個“）”或者一個“ (”
以后每級計算時，如果遇到剩余 n>0個“(”的方案，可以在末尾增加一個“ (”或者“ )”進入下一級；遇到剩余 n=0個“(”的方案，可以在末尾增加一個“ (”進入下一級。

奇數級只能包含剩余奇數個“（”的排列方案
偶數級只能包含剩余偶數個“（”的排列方案

從表中可以看出，灰色部分可以不用計算。

解法

關鍵代碼為：

      
        double
      
       Catalan(
      
        int
      
       n)
        {
            
      
        if
      
       (n == 0) 
      
        return
      
       1; 
      
        for
      
       (
      
        int
      
       i = 2; i <= 2 * n; i++)
            {
                var m = i <= n ? i : 2 * n + 1 - i;
                
      
        for
      
       (
      
        int
      
       j = (i - 1) & 1; j <= m; j += 2)
                {
                    
      
        if
      
       (j > 0) arr[j - 1] += arr[j];
                    
      
        if
      
       (j < n) arr[j + 1] += arr[j];

                    arr[j] = 0;
                }
            }
            
      
        return
      
       arr[0];
        }
    

其中：
n為 Cn中的 n；
arr = new double[n + 1];//arr代表有 k個括弧的時候，剩余 "("個數為 i的排列方案個數 arr[1] = 1;

討論

算法復雜度為 = O(n^2)，空間復雜度為 O(n+1)。相對于利用公式計算而言，此方法的優勢在于——沒有乘除法，只有加法。