整數(shù)劃分 －－－ 一個(gè)老生長(zhǎng)談的問題:
　　1) 練練組合數(shù)學(xué)能力.
　　2) 練練遞歸思想
　　3) 練練DP
　　總之是一道經(jīng)典的不能再經(jīng)典的題目:
　　這道好題求:
　　1. 將n劃分成若干正整數(shù)之和的劃分?jǐn)?shù)。
　　2. 將n劃分成k個(gè)正整數(shù)之和的劃分?jǐn)?shù)。
　　3. 將n劃分成最大數(shù)不超過k的劃分?jǐn)?shù)。
　　4. 將n劃分成若干奇正整數(shù)之和的劃分?jǐn)?shù)。
　　5. 將n劃分成若干不同整數(shù)之和的劃分?jǐn)?shù)。

?

1.將n劃分成不大于m的劃分法：?

?　　1).若是劃分多個(gè)整數(shù)可以存在相同的：

?　　 dp[n][m]= dp[n][m-1]+ dp[n-m][m]??dp[n][m]表示整數(shù) n 的劃分中，每個(gè)數(shù)不大于 m 的劃分?jǐn)?shù)。
?????　　則劃分?jǐn)?shù)可以分為兩種情況:
?????　　a.劃分中每個(gè)數(shù)都小于 m，相當(dāng)于每個(gè)數(shù)不大于 m- 1, 故劃分?jǐn)?shù)為 dp[n][m-1].
????　　?b.劃分中有一個(gè)數(shù)為 m. 那就在 n中減去 m ,剩下的就相當(dāng)于把 n-m 進(jìn)行劃分， 故劃分?jǐn)?shù)為 dp[n-m][m];

　　2).若是劃分多個(gè)不同的整數(shù)：

　　dp[n][m]= dp[n][m-1]+ dp[n-m][m-1]?? dp[n][m]表示整數(shù) n 的劃分中，每個(gè)數(shù)不大于 m 的劃分?jǐn)?shù)。
???　　?同樣劃分情況分為兩種情況：
????　　a.劃分中每個(gè)數(shù)都小于m,相當(dāng)于每個(gè)數(shù)不大于 m-1,劃分?jǐn)?shù)為 dp[n][m-1].
????　　b.劃分中有一個(gè)數(shù)為 m.在n中減去m,剩下相當(dāng)對(duì)n-m進(jìn)行劃分，

　　　并且每一個(gè)數(shù)不大于m-1，故劃分?jǐn)?shù)為 dp[n-m][m-1]

　　2.將n劃分成k個(gè)數(shù)的劃分法：

　dp[n][k]= dp[n-k][k]+ dp[n-1][k-1];

?? 　　方法可以分為兩類：
?? 　　　　第一類: n 份中不包含 1 的分法，為保證每份都 >= 2，可以先拿出 k 個(gè) 1 分
?? 　　到每一份，然后再把剩下的 n- k 分成 k 份即可，分法有: dp[n-k][k]
??　　 　　第二類: n 份中至少有一份為 1 的分法，可以先那出一個(gè) 1 作為單獨(dú)的1份，剩
?? 　　下的 n- 1 再分成 k- 1 份即可，分法有：dp[n-1][k-1]

　　3.將n劃分成若干奇數(shù)的劃分法：（不懂）

　　　　g[i][j]:將i劃分為j個(gè)偶數(shù)

　　　　f[i][j]:將i劃分為j個(gè)奇數(shù)
　　???g[i][j] = f[i - j][j];
???　　f[i][j] = f[i - 1][j - 1] + g[i - j][j];

?

　　　　路過的大牛求解釋，謝謝~

　　代碼如下所示：

/*
?*?hit1402.c
?*
?*??Created?on:?2011-10-11
?*??????Author:?bjfuwangzhu
?*/

#include#include#define?nmax?51
int?num[nmax][nmax];?//將i劃分為不大于j的個(gè)數(shù)
int?num1[nmax][nmax];?//將i劃分為不大于j的不同的數(shù)
int?num2[nmax][nmax];?//將i劃分為j個(gè)數(shù)
int?f[nmax][nmax];?//將i劃分為j個(gè)奇數(shù)
int?g[nmax][nmax];?//將i劃分為j個(gè)偶數(shù)
void?init()?{
????int?i,?j;
????for?(i?=?0;?i?<?nmax;?i++)?{
????????num[i][0]?=?0,?num[0][i]?=?0,?num1[i][0]?=?0,?num1[0][i]?=?0,?num2[i][0]?=
????????????????0,?num2[0][i]?=?0;
????}
????for?(i?=?1;?i?<?nmax;?i++)?{
????????for?(j?=?1;?j?<?nmax;?j++)?{
????????????if?(i?<?j)?{
????????????????num[i][j]?=?num[i][i];
????????????????num1[i][j]?=?num1[i][i];
????????????????num2[i][j]?=?0;
????????????}?else?if?(i?==?j)?{
????????????????num[i][j]?=?num[i][j?-?1]?+?1;
????????????????num1[i][j]?=?num1[i][j?-?1]?+?1;
????????????????num2[i][j]?=?1;

????????????}?else?{
????????????????num[i][j]?=?num[i][j?-?1]?+?num[i?-?j][j];
????????????????num1[i][j]?=?num1[i][j?-?1]?+?num1[i?-?j][j?-?1];
????????????????num2[i][j]?=?num2[i?-?1][j?-?1]?+?num2[i?-?j][j];
????????????}
????????}
????}
????f[0][0]?=?1,?g[0][0]?=?1;
????for?(i?=?1;?i?<?nmax;?i++)?{
????????for?(j?=?1;?j?<=?i;?j++)?{
????????????g[i][j]?=?f[i?-?j][j];
????????????f[i][j]?=?f[i?-?1][j?-?1]?+?g[i?-?j][j];
????????}
????}
}
int?main()?{
#ifndef?ONLINE_JUDGE
????freopen("data.in",?"r",?stdin);
#endif
????int?n,?k,?i,?res0,?res1,?res2,?res3,?res4;
????init();
????while?(~scanf("%d?%d",?&n,?&k))?{
????????res0?=?num[n][n];
????????res1?=?num2[n][k];
????????res2?=?num[n][k];
????????for?(i?=?0,?res3?=?0;?i?<=?n;?i++)?{
????????????res3?+=?f[n][i];
????????}
????????res4?=?num1[n][n];
????????printf("%dn%dn%dn%dn%dnn",?res0,?res1,?res2,?res3,?res4);
????}
????return?0;
}

將正整數(shù)劃分成連續(xù)的正整數(shù)之和
如15可以劃分成4種連續(xù)整數(shù)相加的形式：
15
7 8
4 5 6
1 2 3 4 5

??? 首先考慮一般的形式，設(shè)n為被劃分的正整數(shù)，x為劃分后最小的整數(shù)，如果n有一種劃分，那么
結(jié)果就是x,如果有兩種劃分，就是x和x x + 1， 如果有m種劃分，就是 x 、x x + 1 、 x x + 1 x + 2 、... 、x x + 1 x + 2 ... x + m - 1
將每一個(gè)結(jié)果相加得到一個(gè)公式(i * x + i * (i - 1) / 2) = n，i為當(dāng)前劃分后相加的正整數(shù)個(gè)數(shù)。
滿足條件的劃分就是使x為正整數(shù)的所有情況。
如上例，當(dāng)i = 1時(shí)，即劃分成一個(gè)正整數(shù)時(shí)，x = 15， 當(dāng)i = 2時(shí)， x = 7。
當(dāng)x = 3時(shí)，x = 4， 當(dāng)x = 4時(shí)，4/9，不是正整數(shù)，因此，15不可能劃分成4個(gè)正整數(shù)相加。
當(dāng)x = 5時(shí)，x = 1。

??? 這里還有一個(gè)問題，這個(gè)i的最大值是多少？不過有一點(diǎn)可以肯定，它一定比n小。我們可以做一個(gè)假設(shè)，
假設(shè)n可以拆成最小值為1的劃分，如上例中的1 2 3 4 5。這是n的最大數(shù)目的劃分。如果不滿足這個(gè)假設(shè)，
那么 i 一定比這個(gè)劃分中的正整數(shù)個(gè)數(shù)小。因此可以得到這樣一個(gè)公式i * (i + 1) / 2 <= n，即當(dāng)i滿足
這個(gè)公式時(shí)n才可能被劃分。

代碼如下：

void?split(int?n)?{
????int?i,?j,?te,?x,?xlen;
????for?(i?=?1,?xlen?=?0;?(te?=?i?*?(i?-?1)?/?2)?<?n;?i++)?{
????????x?=?n?-?te;
????????if?(x?%?i?==?0)?{
????????????x?/=?i;
????????????printf("%d",?x);
????????????for?(j?=?1;?j?<?i;?j++)?{
????????????????printf("%d?",?x?+?j);
????????????}
????????????printf("n");
????????????xlen++;
????????}
????}
????printf("%dn",?xlen);
}

?

以下是轉(zhuǎn)載的：

　　求劃分因子乘積最大的一個(gè)劃分及此乘積
　　問題簡(jiǎn)述：給定一個(gè)正整數(shù)n, 則在n所有的劃分中, 求因子乘積最大的一個(gè)劃分及此乘積。例如：8 = {8}, {7, 1}, {6, 2}, {5, 3}, {4, 4}, {3, 3, 2}, {2, 2, 2, 2} 等，那么在這些當(dāng)中，3 * 3 * 2 的乘積最大，所以輸出整個(gè)劃分
和這個(gè)乘積 18。
　　算法分析：這是我在某個(gè)論壇上看到的問題，以及別人針對(duì)此問題的數(shù)學(xué)分析，現(xiàn)簡(jiǎn)單的整理如下：
　　(1)對(duì)于任意大于等于4的正整數(shù)m, 存在一個(gè)劃分m = m1+m2, 使 m1*m2 >= m證: 令m1 = int(m/2), 則 m1 >= 2 ， m2 = m-m1; 那么m2 > 2，并且 m2 >= m/2 >= m1;??? m1*m2 >= 2*m2 >= m; 證畢;
該證明簡(jiǎn)單的來說就是：對(duì)于一個(gè)大于等于4的正整數(shù)m，存在一個(gè)2塊劃分的因子，這兩個(gè)因子的乘積總是不小于原數(shù)m本身。
　　(2)由(1)知此數(shù)最終可以分解為 2^r * 3^s。現(xiàn)證明 r <= 2;
　　證：若r > 2, 則至少有3個(gè)因子為2, 而2*2*2 < 3*3;
　　所以可以將3個(gè)為2的因子,換為兩個(gè)因子3；積更大；證畢。
　　綜合(1)，(2)，則有：任何大于4的因子都可以有更好的分解, 而4可以分解為2*2。
　　所以：此數(shù)應(yīng)該分解為 2^k1 * 3^k2。而且可以證明 k1>=0 并且 k1 <= 2，因此：
　　?? A.當(dāng)n = 3*r 時(shí), 分解為 3^r
?　　? B.當(dāng)n = 3*r+1時(shí), 分解為 3^(r-1)*2*2
?? 　　C.當(dāng)n = 3*r+2時(shí), 分解為 3^r*2
　　剩下編程處理，那就是太簡(jiǎn)單了，首先是處理

?

　　小學(xué)六年級(jí)奧數(shù)---整數(shù)劃分(有用結(jié)論)

　　例1：把14分拆成若干個(gè)自然數(shù)的和，再求出這些數(shù)的積，要使得到的積最大，應(yīng)該把14如何分拆？這個(gè)最大的乘積是多少？

　　分析與解：我們先考慮分成哪些數(shù)時(shí)乘積才能盡可能地大。
　　首先，分成的數(shù)中不能有1，這是顯然的。
　　其次，分成的數(shù)中不能有大于4的數(shù)，否則可以將這個(gè)數(shù)再分拆成2與另外一個(gè)數(shù)的和，這兩個(gè)數(shù)的乘積一定比原數(shù)大，例如7就比它分拆成的2和5的乘積小。
　　再次，因?yàn)?=2×2，故我們可以只考慮將數(shù)分拆成2和3。
　　注意到2+2+2=6，2×2×2=8；3+3=6，3×3=9，因此分成的數(shù)中若有三個(gè)2，則不如換成兩個(gè)3，換句話說，分成的數(shù)中至多只能有兩個(gè)2，其余都是3。根據(jù)上面的討論，我們應(yīng)該把14分拆成四個(gè)3與一個(gè)2之和，即14=3+3+3+3+2，這五數(shù)的積有最大值 3×3×3×3×2=162。
　　將上述結(jié)論推廣為一般情形便是：
　　把自然數(shù)S（S＞1）分拆為若干個(gè)自然數(shù)的和：?? S=a1+a2+…+an，則當(dāng)a1，a2，…，an中至多有兩個(gè)2，其余都是3時(shí)，其連乘積m=a1a2…an有最大值。

　　例2：把1993分拆成若干個(gè)互不相等的自然數(shù)的和，且使這些自然數(shù)的乘積最大，該乘積是多少？
解：由于把1993分拆成若干個(gè)互不相等的自然數(shù)的和的分法只有有限種，因而一定存在一種分法，使得這些自然數(shù)的乘積最大。
　　若1作因數(shù)，則顯然乘積不會(huì)最大。把1993分拆成若干個(gè)互不相等的自然數(shù)的和，因數(shù)個(gè)數(shù)越多，乘積越大。為了使因數(shù)個(gè)數(shù)盡可能地多，我們把1993分成2+3…+n直到和大于等于1993。
若和比1993大1，則因數(shù)個(gè)數(shù)至少減少1個(gè)，為了使乘積最大，應(yīng)去掉最小的2，并將最后一個(gè)數(shù)（最大）加上1。
若和比1993大k（k≠1），則去掉等于k的那個(gè)數(shù)，便可使乘積最大。
所以n=63。因?yàn)?015-1993=22，所以應(yīng)去掉22，把1993分成（2+3+…+21）+（23+24+…+63）

這一形式時(shí)，這些數(shù)的乘積最大，其積為? 2×3×…×21×23×24×…×63。