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

問題

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

卡特蘭數(shù)真是一個(gè)神奇的數(shù)字，很多組合問題的數(shù)量都和它有關(guān)系，例如：

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

XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY

• Cn= n對(duì)括號(hào)正確匹配組成的字符串?dāng)?shù)，例如 3對(duì)括號(hào)能夠組成：

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

• Cn= n+1個(gè)數(shù)相乘，所有的括號(hào)方案數(shù)。例如， 4個(gè)數(shù)相乘的括號(hào)方案為：

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

• Cn= 擁有 n+1 個(gè)葉子節(jié)點(diǎn)的二叉樹的數(shù)量。例如 4個(gè)葉子節(jié)點(diǎn)的所有二叉樹形態(tài)：

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

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

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

在《Enumerative Combinatorics》一書中，竟然提到了多達(dá) 66種組合問題和卡特蘭數(shù)有關(guān)。

分析

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

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

奇數(shù)級(jí)只能包含剩余奇數(shù)個(gè)“（”的排列方案
偶數(shù)級(jí)只能包含剩余偶數(shù)個(gè)“（”的排列方案

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

解法

關(guān)鍵代碼為：

      
        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個(gè)括弧的時(shí)候，剩余 "("個(gè)數(shù)為 i的排列方案個(gè)數(shù) arr[1] = 1;

討論

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