<pre>
整數(shù)劃分問(wèn)題是算法中的一個(gè)經(jīng)典命題之一令杈，有關(guān)這個(gè)問(wèn)題的講述在講解到遞歸時(shí)基本都將涉及掖举。所謂整數(shù)劃分隅忿，是指把一個(gè)正整數(shù)n寫成如下形式:</br></br>
n=m1+m2+...+mi; （其中mi為正整數(shù)膊爪，并且1 <= mi <= n）入客，則{m1,m2,...,mi}為n的一個(gè)劃分管毙。</br></br>
如果{m1,m2,...,mi}中的最大值不超過(guò)m腿椎，即max(m1,m2,...,mi)<=m桌硫，則稱它屬于n的一個(gè)m劃分。這里我們記n的m劃分的個(gè)數(shù)為f(n,m);</br></br>
例如但n=4時(shí)啃炸，有5個(gè)劃分铆隘，{0,0,0,4},{0,0,3,1},{0,0,2,2},{0,2,1,1},{1,1,1,1};</br></br>
注意{0,0,1,3} 和 {0,0,3,1}被認(rèn)為是同一個(gè)劃分。</br></br>
該問(wèn)題是求出n的所有劃分個(gè)數(shù)南用，即f(n, n)膀钠。下面我們考慮求f(n,m)的方法;
</pre></br>
<a>遞歸法</a></br>
根據(jù)n和m的關(guān)系，考慮以下幾種情況：</br>
（1）當(dāng) n = 1 時(shí)裹虫，不論m的值為多少（m > 0 )肿嘲，只有一種劃分即 { 1 };
<pre><code> 因此 f(1, m) = 1;</code></pre></br>
（2）當(dāng) m = 1 時(shí)，不論n的值為多少筑公，只有一種劃分即 n 個(gè) 1雳窟，{ 1, 1, 1, ..., 1 };</br>
<pre><code> 因此 f(n, 1) = 1;</code></pre></br>
（3）當(dāng) n = m 時(shí)，根據(jù)劃分中是否包含 n匣屡，可以分為兩種情況：
a. 劃分中包含n的情況封救，只有一個(gè)即 { n }；
b. 劃分中不包含n的情況捣作，即劃分中最大的數(shù)字也比 n 小誉结，也就是 n 的所有 ( n - 1 ) 劃分。
<pre><code> 因此 f(n, n) = 1 + f(n, n-1);</code></pre></br>
（4）當(dāng) n < m 時(shí)券躁，由于劃分中不可能出現(xiàn)負(fù)數(shù)惩坑，因此就相當(dāng)于 f(n, n)， 轉(zhuǎn)至第三種情況;</br></br>
（5） 但 n > m 時(shí)也拜，根據(jù)劃分中是否包含最大值 m以舒，可以分為兩種情況：
a. 劃分中包含 m 的情況，即 { m, { x1, x2, ..., xi } }, 其中 { x1, x2, ..., xi } 的和為 （n - m）搪泳，可能再次出現(xiàn) m稀轨，因此是（n - m）的 m 劃分，因此這種劃分個(gè)數(shù)為 f(n-m, m);
b. 劃分中不包含 m 的情況岸军，則劃分中所有值都比 m 小奋刽，即 n 的 ( m - 1 ) 劃分瓦侮，個(gè)數(shù)為 f(n, m - 1);
<pre><code> 因此 f(n, m) = f(n - m, m) + f(n, m - 1);</code></pre>
綜合以上情況，我們可以看出佣谐，上面的結(jié)論具有遞歸定義特征肚吏，其中（1）和（2）屬于回歸條件，（3）和（4）屬于特殊情況狭魂，將會(huì)轉(zhuǎn)換為情況（5）罚攀。而情況（5）為通用情況，屬于遞推的方法雌澄，其本質(zhì)主要是通過(guò)減小m以達(dá)到回歸條件斋泄，從而解決問(wèn)題。其遞推表達(dá)式如下：
<pre><code>
f(n, m) = 1; ( n = 1 or m = 1 )
f(n, n); ( n < m )
1+ f(n, m - 1); ( n = m )
f(n - m, m) + f(n, m - 1); ( n > m )
</code></pre>
</br>
給出代碼如下（c/c++實(shí)現(xiàn)）
<pre>
<code>
int f(int i, int j)
{
int ret;
if (j == 1 || i == 1)//情況（1）,（2）
return 1;
else if (i == j)//情況（3）
ret = 1 + f(i,j-1);
else if (i < j)//情況（4）
ret = f(i, i);
else if (i > j)//情況（5）
ret = f(i-j,j) + f(i,j-1);
return ret;
}
</code>
</pre>
</br>
注：本文原稿摘自http://www.cnblogs.com/hoodlum1980/archive/2008/10/11/1308493.html
