整數分拆

（5）當n>m時，根據劃分中是否包含m，可以分為兩種情況：

（a）劃分中包含 的情況，即{m,{x1,x2,x3,...,xi}}，其中{x1,x2,x3,...,xi}的和為n-m，可能再次出現m，因此是（n-m）的m劃分，因此這種劃分個數為f(n-m,m；

（b）劃分中不包含m的情況，則劃分中所有值都比m小，即n的（m-1）劃分，個數為f(n,m-1；

因此，f(n,m)=f(n-m,m)+f(n,m-1)。

綜合以上各種情況，可以看出，上面的結論具有遞歸定義的特徵，其中（1）和（2）屬於回歸條件，（3）和（4）屬於特殊情況，而情況（5）為通用情況，屬於遞歸的方法，其本質主要是通過減少n或m以達到回歸條件，從而解決問題。

詳細遞推公式描述如下：

參考源碼

這個版本的時間複雜度較高，運行效率很低。

考慮到在上一節使用遞歸中，很多的子遞歸重複計算。如在計算 f (10,9)時，劃分成為 f (1,9) + f (10,8)，進一步劃分為 f (1,1)=f (2,8)+f (10,7)，接下來轉換為f (1,1) +f (2,2)+ f (3,7)+ f (10,6) =3* f (1,1) +1+ f (3,7)+ f (10,6)，這樣就產生了重複，然而，在遞歸的時候，每個都需要被計算一遍，因此可見，位於底層的狀態，計算的次數也越來越多。這樣在時間開銷特別大，是造成運算慢的根本原因，比如算120的時候需要3秒中，計算130的時候需要27秒鐘，在計算機200的時候....計算10分鐘還沒計算出來。

鑒於此，我們已經分析出了普通遞推關係中存在大量的冗餘造成了重複計算，最終導致了運行時間太長，一種自然地想法是能夠用一種技巧，以避免重複計算？這裡我們使用動態規劃的思想進行程序設計。

在上一節中，已經分析了狀態轉移的方程，因此，我們在求解子問題時，利用標記的思想，首先檢查產生的子問題是否在之前被計算過，這是因為對於相同的子問題，得到的結果肯定是一樣的，因此利用這一步去掉冗餘的操作，極大減少了計算的時間開銷。對於沒有標記的子問題來說，一定是沒有被計算過，這樣，在計算完成後，順便標記一下子問題，以確保以後不用再重複計算。利用這個特性，可以確保所有的劃分子問題都無重複，無遺漏的恰巧被計算一次。

動態規劃版主要是利用了標記思想進行加速。

參考源碼如下：

這樣的演演算法效率快了很多。

對於整數拆分問題，也可以從另一個角度，即“母函數”的角度來考慮這個問題。所謂母函數，即為關於x的一個多項式，滿足：

則我們稱為序列 的母函數。我們從整數劃分考慮，假設的某個劃分中，1的出現個數記為，2的個數記為，…，的個數 記為顯然有：

因此 的劃分數，也就是從1到 這 個數字的組合，每個數字理論上可以無限重複出現，即個數隨意，使它們的和為。顯然，數字 可以有如下可能，出現0次（即不出現），1次，2次，…，次等等。把數字用 表示，出現 次的數字用 表示，不出現用1表示。例如，數字2用 表示，2個2用 表示，3個2用 表示，k個2用 表示。則對於從1到 的所有可能組合結果我們可以表示為：

上面的表達式中，每個括弧內的多項式代表了數字的參與到劃分中的所有可能情況。因此，該多項式展開后，由於，因此 就代表了 的劃分，展開後項的係數也就是的所有劃分個數，即。

由此我們找到了關於整數劃分的母函數，剩下的問題就是，我們需要求出 的展開后的所有係數。為此，我們首先要做多項式乘法，對於計算機編程來說，並不困難。我們把一個關於 的多項式用一個整數數組 表示，代表 的係數，然後卷積即可。

參考源碼：

這樣基於生成函數的方法實際上快了很多。

設第n個五邊形數為，那麼，即序列為：1, 5, 12, 22, 35, 51, 70, ...

對應圖形如下：

設五邊形數的生成函數為，那麼有：

以上是五邊形數的情況。下面是關於五邊形數定理的內容：

五邊形數定理是一個由歐拉發現的數學定理，描述歐拉函數展開式的特性。歐拉函數的展開式如下：

即：

可見，歐拉函數展開后，有些次方項被消去，只留下次方項為1, 2, 5, 7, 12, ...的項次，留下來的次方恰為廣義五邊形數。

五邊形數和分割函數的關係：歐拉函數的倒數是分割函數的母函數，亦即：

其中 為 的分割函數。上式配合五邊形數定理，有：

在 時，等式右側的係數均為0，比較等式二側的係數，可得

因此可得到分割函數的遞歸式：

所以，通過上面遞歸式，我們可以很快速地計算的整數劃分方案數了。

參考代碼：

以上設計的代碼是最高效的。

通過比較上述四種演演算法，可見整數拆分的劃分方法比較多樣，且不同的演演算法運行效率差距比較大，需要仔細理解和思考。