题目标题： 整数划分 spa

/*

动态规划dp问题，网上给的说明很详细了。

第一行和第三行：

对于第一行和第三行，根据状态转移方程很容易写出：

dp[i][j] = dp[i][i]                j>i 时

= dp[i-j][j]+dp[i][j-1]   i>=j 时

i 记录的是该要分的数,j表示最大数不超过j的划分数，当j比i还大时当然是只能j分到i而已，

当i>=j时，注意到5 = 5 = 4+1 = 3+2 = 3+1+1 = 2+2+1 = 2+1+1+1 = 1+1+1+1+1，5可以划分为

+1 ，而4的划分数之前已求出，相当于加上4的划分数，即dp[i][j-1]，另外注意到

= 2+2+1 = 2+1+1+1 = 1+1+1+1+1 ，即还要加上要减的数5减掉2之后,

dp[5][2] = dp[5-2][2]+dp[5][1] = dp[3][2]+1 = dp[3-2][2]+dp[3][1]+1 = dp[1][1]+1+1 = 3;

每次算dp时其实都可以先写写dp之间的转移关系，弄清楚后，再写出状态转移方程

第二行：

将n划分成K个正整数之和的划分数。根据第一行和第三行的程序的启发，可以这样设置dp为三维，

dp[i][p][j] ，i表示要划分的数，p为要划分的总个数，j为划分的数中的最大值为不超过j，可以得到

以下状态转移方程：

dp[i][p][j] = dp[i][p][i]                j>i 时

= dp[i-j][p-1][j] + dp[i][p][j-1]

解析一下吧：

当没用到当前最大值j时，因为要划分的数和要划分的数的个数都不变，

当用到当前最大值j时，因为用到了一个数，所以划分数的总个数减一，并且划分数要减j

初始化可以是先置零，再dp[i][1][j] = 1,且当j>i时，dp[i][p][j] = dp[i][p][i]

比如例子：

dp[5][2][5] = dp[0][1][5]+dp[5][2][4] = 0+dp[1][1][4]+dp[5][2][3] = 1+dp[5][2][3]

= 1+dp[2][1][3] = 2 ，得到结果

第四行：

将n划分成若干奇正整数之和的划分数。同样根据一三行的方法做，令dp[i][j]表示当前的划

分数为i，最大值为j时的中的划分数，则状态转移方程为

dp[i][j] = dp[i][i]        if(j%2==1&&j>i)

= dp[i][i-1]   if(j%2==0&&j>i)

= dp[i-j][j]+dp[i][j-2]

解析一下：

当j>i时没什么好说的了，因为最大数不可能为偶数嘛，

当j<=i时，如果用到当前最大值，则划分数要减掉当前的j值，

如果没用到j时，则划分数不变，划分的最大值要减少2

第五行：

将n划分成若干不同整数之和的划分数。其实这个的状态转移方程挺好找的，

同样根据一三的方法就行，dp[i][j] = dp[i][j-1]+dp[i-j][j-1]，

解析一下：

i 记录的是要划分的数，j表示当前最大划分到的数中的最大值，

当用到当前的j时，划分数i要减掉j，并且因为各个划分数不同，所以j还要减掉1；

当没用到j时，j减一，划分数i不变

由此看来，第一行和第三行的代码很重要，其他的都是可以从它得到啊。。。

*/

#include<stdio.h>

#include<string.h>

#define X 52

int dp[X][X],dp2[X][X][X],dp3[X][X],dp4[X][X],n,k;

int i,j;

void f_1_3()

{

for(i=1;i<X;i++)    // 初始化

dp[i][0] = 0;

dp[0][0] = 1;

for(i=0;i<X;i++)    // 实现状态转移方程

for(j=1;j<X;j++)

if(i>=j)

dp[i][j] = dp[i-j][j]+dp[i][j-1];

else

dp[i][j] = dp[i][i];

}

void f_2()

{

memset(dp2,0,sizeof(dp2));

for(i=1;i<X;i++)    // 初始化

dp2[i][1][i] = 1;

for(i=0;i<X;i++)    // 初始化

for(j=0;j<X;j++)

if(j>i)

dp2[i][1][j] = dp2[i][1][i];

for(i=1;i<X;i++)    // 状态转移

for(int p=2;p<X;p++)

for(j=1;j<X;j++)

if(j>i)

dp2[i][p][j] = dp2[i][p][i];

else

dp2[i][p][j] = dp2[i-j][p-1][j]+dp2[i][p][j-1];

}

void f_4()

{

memset(dp3,0,sizeof(dp3));

for(i=1;i<X;i++)    // 初始化，当最大值为1时，只能由i自己本身组成，划分数为1

dp3[i][1] = 1;

for(i=1;i<X;i+=2)    // 涉及到后面的状态转移时i会减少到0，但实际上，当j为奇数时，必须得加1

dp3[0][i] = 1;

dp3[0][0] = 1;            // 初始化1

for(i=1;i<X;i++)    // 实现状态转移方程

for(j=3;j<X;j+=2)

{

if(j>i)

{

if(i%2)

dp3[i][j] = dp3[i][i];

else

dp3[i][j] = dp3[i][i-1];

}

else

dp3[i][j] = dp3[i-j][j]+dp3[i][j-2];

}

}

void f_5()

{

memset(dp4,0,sizeof(dp4));

for(i=1;i<X;i++)    // 初始化

{

dp4[1][i] = 1;

dp4[0][i] = 1;

}

for(i=2;i<X;i++)    // 状态转移方程

for(j=1;j<X;j++)

if(i<j)

dp4[i][j] = dp4[i][i];

else

dp4[i][j] = dp4[i][j-1]+dp4[i-j][j-1];

}

int main()

{

f_1_3();

f_2();

f_4();

f_5();

while(scanf("%d%d",&n,&k)!=EOF)

{

printf("%d\n",dp[n][n]);

printf("%d\n",dp2[n][k][n]);

printf("%d\n",dp[n][k]);

if(n%2)

printf("%d\n",dp3[n][n]);

else

printf("%d\n",dp3[n][n-1]);

printf("%d\n\n",dp4[n][n]);

}

return 0;

}