動态規劃求解所有字元的組合數

一，問題描述

給定若幹個字元，求解 這些字元能夠表示的最多組合個數。比如{'a','b','c'} 一共有七種組合。(每種組合沒有重複的字元 且 組合的種數與順序無關，如 ab 和 ba 是同一種組合)

a、b 、c 、ab 、ac 、bc 、abc

其實，求組合個數，可以用公式來求解:具給定 n種字元，一共有  c(n,1)+c(n,2)+...+c(n,n)種不同的組合。其中，c(n,i)表示：從n個字元中任選 i 個的組合數，數學表示為：C in。

二，DP算法思路

既然已經可以用上面的公式 c(n,1)+c(n,2)+...+c(n,n) 來計算不同的組合數了，那為什麼還用DP？因為，上面的公式隻能給定組合數，但是不能給出具體是哪些組合。

假設輸入 m 個字元（互不相同），則這些字元隻能構成長度為 1,2,....m 的組合，設某個組合的長度為 n。即： 1 =< n <= m

設 c[m][n] 表示 使用 m 種不同的字元，表示長度最多為 n 的組合個數 的最大值。

最大值 展現了最優子問題性質。最優子問題分析如下：把字元組合分成兩部分，第一個字元 以及剩下的所有字元。

對于第 m 種字元而言，隻有兩種情況：①是字元組合的第一個字元，②不是在字元組合的第一個字元。是以，可以應用《組合數學》中的加法原理。（比如 'abc' 就是一個字元組合）

c[m][n]=c[m-1][n-1] + c[m-1][n]

c[m-1][n-1]，表示第 m 個字元是字元組合中的第一個字元。此時，該問題變成：用 1,2,...m-1個字元(共 m-1 種) 來 組合 長度為 n-1的 字元組合(‘字元串’)

c[m-1][n]，表示第 m 個字元不是 字元組合中的第一個字元。此時，該問題變成：在剩餘的 m-1種字元裡面選出 n 個字元來組合。？？？（有點不太對）

'm' ? ? .... ?             第一個字元是 'm'

'*'  ? ? .....?             第一個字元不是 'm'

注意，原問題表示的字元組合 長度是 n

三，代碼實作

對于初始條件的确定，可以先畫一個小的示例圖來确定。比如：allCombination({'a','b','c'}, 3)......

在代碼裡面 記錄下具體選了哪些字元，就可以列印輸出具有的字元組合了。其實我也不會。

時間複雜度分析：從上面的遞歸方法來看：遞歸表達式為 T(m)=2T(m-1)，得出：T(m)=2^m ，指數級複雜度

而從上面的動态規劃求解方法來看：時間複雜度為O(m^2)

（動态規劃的兩個基本特征：①最優子結構；②重疊子問題）

四，參考資料

http://www.cnblogs.com/hapjin/p/5579737.html

http://wuchong.me/blog/2014/07/28/permutation-and-combination-realize/

本文轉自hapjin部落格園部落格，原文連結：http://www.cnblogs.com/hapjin/p/5583577.html，如需轉載請自行聯系原作者