這道題吃了翔，尼瑪有沒說多case。。。
通過這道題，初步了解了整數劃分的經典問題，值得。
一 求将n劃分為若幹正整數之和的劃分數
1. 若劃分的多個整數可以相同
設dp[i][j]為将i劃分為不大于j的劃分數
(1) 當i<j 時，i不能劃分為大于i的數，是以dp[i][j]=dp[i][i]；
(2) 當i>j 時，可以根據劃分中是否含有j分為兩種情況。若劃分中含有j，劃分方案數為dp[i-j][j]；若劃分數中不含j，相當于将i劃分為不大于j-1的劃分數，為dp[i][j-1]。是以當i>j時dp[i][j]=dp[i-j][j]+dp[i][j-1]；
(3) 當i=j 時，若劃分中含有j隻有一種情況，若劃分中不含j相當于将i劃分為不大于j-1的劃分數。此時dp[i][j]=1+dp[i][j-1]。
dp[n][n]可以解決問題1，dp[n][k]表示将n劃分為最大數不超過k的劃分數，可以解決問題3。
2. 若劃分的正整數必須不同
設dp[i][j]為将i劃分為不超過j的不同整數的劃分數
(1) 當i<j時，i不能劃分為大于i的數，是以dp[i][j]=dp[i][i]；
(2) 當i>j時，可以根據劃分中是否含有j分為兩種情況。若劃分中含有j，則其餘的劃分中最大隻能是j-1，方案數為dp[i-j][j-1]；若劃分中不含j，相當于将i劃分為不大于j-1的劃分數，為dp[i][j-1]。是以當i>j時dp[i][j]=dp[i-j][j-1]+dp[i][j-1]；
(3) 當i=j時，若劃分中含有j隻有一種情況，若劃分中不含j相當于将i劃分為不大于j-1的劃分數。此時dp[i][j]=1+dp[i][j-1]
dp[n][n]表示将n劃分為不同整數的劃分數，可以解決問題5.
二 将n劃分為k個整數的劃分數
設dp[i][j]為将i劃分為j個整數的劃分數。
(1) i<j為不可能出現的情況，dp[i][j]=0；
(2) 若i=j，有一種情況：i可以劃分為i個1之和，dp[i][j]=1；
(3) 若i>j，可以根據劃分數中是否含有1分為兩類：若劃分數中含有1，可以使用“截邊法”将j個劃分分别截去一個1，把問題轉化為i-j的j-1個劃分數，為dp[i-j][j-1]； 若劃分中不包含1，使用“截邊法”将j個劃分數的最下面一個數截去，将為題轉化為求i-j的j個劃分數，為dp[i-j][j]。是以i>j時dp[i][j]=dp[i-j][j-1]+dp[i-j][j]。
dp[n][k]為将n劃分為k個整數的劃分數，可解決問題2。
三 将n劃分為若幹正奇數之和的劃分數
設f[i][j]為将i劃分為j個奇數之和的劃分數，g[i][j]為将i劃分為j個偶數之和的劃分數。
使用截邊法，将g[i][j]的j個劃分都去掉1，可以得到f[i-j][j]，是以
g[i][j] = f[i-j][j]。
f[i][j]中有包含1的劃分方案和不包含1的劃分方案。對于包含1的劃分方案，可以将1的劃分除去，轉化為“将i-1劃分為j-1個奇數之和的劃分數”，即f[i-1][j-1]；對于不包含1的劃分方案，可以使用截邊法對j個劃分每一個都去掉一個1，轉化為“将i-j劃分為j個偶數之和的劃分數”，即g[i-j][j]。
是以f[i][j]=f[i-1][j-1]+g[i-j][j]。
f[n][0]+f[n][1]+……+f[n][n]為将n劃分為若幹奇數的劃分數，為問題4的答案。
四 将正整數劃分成連續的正整數之和
如15可以劃分成4種連續整數相加的形式：
15
7 8
4 5 6
1 2 3 4 5
首先考慮一般的形式，設n為被劃分的正整數，x為劃分後最小的整數，如果n有一種劃分，那麼
結果就是x,如果有兩種劃分，就是x和x x + 1， 如果有m種劃分，就是 x 、x x + 1 、 x x + 1 x + 2 、... 、x x + 1 x + 2 ... x + m - 1
将每一個結果相加得到一個公式(i * x + i * (i - 1) / 2) = n，i為目前劃分後相加的正整數個數。
滿足條件的劃分就是使x為正整數的所有情況。
如上例，當i = 1時，即劃分成一個正整數時，x = 15， 當i = 2時， x = 7。
當x = 3時，x = 4， 當x = 4時，4/9，不是正整數，是以，15不可能劃分成4個正整數相加。
當x = 5時，x = 1。
這裡還有一個問題，這個i的最大值是多少？不過有一點可以肯定，它一定比n小。我們可以做一個假設，
假設n可以拆成最小值為1的劃分，如上例中的1 2 3 4 5。這是n的最大數目的劃分。如果不滿足這個假設，
那麼 i 一定比這個劃分中的正整數個數小。是以可以得到這樣一個公式i * (i + 1) / 2 <= n，即當i滿足
這個公式時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("%d\n", xlen);
}
五 求劃分因子乘積最大的一個劃分及此乘積
問題簡述：給定一個正整數n, 則在n所有的劃分中, 求因子乘積最大的一個劃分及此乘積。例如：8 = {8}, {7, 1}, {6, 2}, {5, 3}, {4, 4}, {3, 3, 2}, {2, 2, 2, 2} 等，那麼在這些當中，3 * 3 * 2 的乘積最大，是以輸出整個劃分
和這個乘積 18。
算法分析：這是我在某個論壇上看到的問題，以及别人針對此問題的數學分析，現簡單的整理如下：
(1)對于任意大于等于4的正整數m, 存在一個劃分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; 證畢;
該證明簡單的來說就是：對于一個大于等于4的正整數m，存在一個2塊劃分的因子，這兩個因子的乘積總是不小于原數m本身。
(2)由(1)知此數最終可以分解為 2^r * 3^s。現證明 r <= 2;
證：若r > 2, 則至少有3個因子為2, 而2*2*2 < 3*3;
是以可以将3個為2的因子,換為兩個因子3；積更大；證畢。
綜合(1)，(2)，則有：任何大于4的因子都可以有更好的分解, 而4可以分解為2*2。
是以：此數應該分解為 2^k1 * 3^k2。而且可以證明 k1>=0 并且 k1 <= 2，是以：
A.當n = 3*r 時, 分解為 3^r
B.當n = 3*r+1時, 分解為 3^(r-1)*2*2
C.當n = 3*r+2時, 分解為 3^r*2
剩下程式設計處理，那就是太簡單了，首先是處理 <= 4的特殊情況，再對>4的情況進行模3的3種情況的判斷，最後一一輸出。可見，數學在整數劃分問題上有太強的功能。誰叫這個問題叫整數劃分呢，不與數學密切才怪! ^_^。
六 國小六年級奧數---整數劃分(有用結論)
例1：把14分拆成若幹個自然數的和，再求出這些數的積，要使得到的積最大，應該把14如何分拆？這個最大的乘積是多少？
分析與解：我們先考慮分成哪些數時乘積才能盡可能地大。
首先，分成的數中不能有1，這是顯然的。
其次，分成的數中不能有大于4的數，否則可以将這個數再分拆成2與另外一個數的和，這兩個數的乘積一定比原數大，例如7就比它分拆成的2和5的乘積小。
再次，因為4=2×2，故我們可以隻考慮将數分拆成2和3。
注意到2+2+2=6，2×2×2=8；3+3=6，3×3=9，是以分成的數中若有三個2，則不如換成兩個3，換句話說，分成的數中至多隻能有兩個2，其餘都是3。根據上面的讨論，我們應該把14分拆成四個3與一個2之和，即14=3+3+3+3+2，這五數的積有最大值 3×3×3×3×2=162。
将上述結論推廣為一般情形便是：
把自然數S（S＞1）分拆為若幹個自然數的和： S=a1+a2+…+an，則當a1，a2，…，an中至多有兩個2，其餘都是3時，其連乘積m=a1a2…an有最大值。
例2：把1993分拆成若幹個互不相等的自然數的和，且使這些自然數的乘積最大，該乘積是多少？
解：由于把1993分拆成若幹個互不相等的自然數的和的分法隻有有限種，因而一定存在一種分法，使得這些自然數的乘積最大。
若1作因數，則顯然乘積不會最大。把1993分拆成若幹個互不相等的自然數的和，因數個數越多，乘積越大。為了使因數個數盡可能地多，我們把1993分成2+3…+n直到和大于等于1993。
若和比1993大1，則因數個數至少減少1個，為了使乘積最大，應去掉最小的2，并将最後一個數（最大）加上1。
若和比1993大k（k≠1），則去掉等于k的那個數，便可使乘積最大。
是以n=63。因為2015-1993=22，是以應去掉22，把1993分成（2+3+…+21）+（23+24+…+63）
這一形式時，這些數的乘積最大，其積為 2×3×…×21×23×24×…×63。
整數劃分代碼：
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
#define N 1001
int dp[N][N],fp[N][N];
int n,k;
void divide1() //将i劃分為不大于j的劃分數
{
for(int i=1; i<=n; i++)
dp[i][1]=1;
for(int i=1; i<=n; i++)
{
for(int j=2; j<=n; j++)
{
if(i<j) dp[i][j]=dp[i][i];
else if(i==j) dp[i][j]=1+dp[i][j-1];
else
dp[i][j]=dp[i-j][j]+dp[i][j-1];
}
}
}
void divide2() //将i劃分為不大于j的不同整數的劃分數
{
dp[1][1]=1;
for(int i=2; i<=n; i++)
dp[i][1]=0;
for(int i=1; i<=n; i++)
{
for(int j=2; j<=n; j++)
{
if(i<j) dp[i][j]=dp[i][i];
else if(i==j) dp[i][j]=1+dp[i][j-1];
else
dp[i][j]=dp[i-j][j-1]+dp[i][j-1];
}
}
}
void divide3() //dp[i][j]表示将i劃分為j個整數之和的劃分數
{
for(int i=1; i<=n; i++)
dp[i][1]=1;
for(int i=1; i<=n; i++)
{
for(int j=2; j<=n; j++)
{
if(i<j) dp[i][j]=0;
else if(i==j) dp[i][j]=1;
else
{
dp[i][j]=dp[i-j][j]+dp[i-1][j-1];
}
}
}
}
int divide4() //dp[i][j]表示将i劃分為j個奇數的劃分數
//fp[i][j]表示将i劃分為j個偶數的劃分數
{
dp[0][0]=fp[0][0]=1;
for(int i=1; i<=n; i++)
for(int j=1; j<=i; j++)
{
fp[i][j]=dp[i-j][j];
dp[i][j]=dp[i-1][j-1]+fp[i-j][j];
}
int sum=0;
for(int i=1; i<=n; i++)
sum+=dp[n][i];
return sum;
}
int main()
{
//FILE *fp;
//int at,bt,ct,dt,et;
//fp=fopen("H:\\codeblocks檔案\\data.txt","r");
while(cin >>n>>k){
int a,b,c,d,e;
divide1();
a=dp[n][n];
c=dp[n][k];
divide2();
e=dp[n][n];
divide3();
b=dp[n][k];
d=divide4();
//fscanf(fp,"%d%d%d%d%d",&at,&bt,&ct,&dt,&et);
//if(at!=a||bt!=b||ct!=c||dt!=d||et!=e)
//cout<<1<<endl;
cout<<a<<endl<<b<<endl<<c<<endl<<d<<endl<<e<<endl<<endl;
}
return 0;
}