整数划分是一个经典的问题。 Input 每组输入是两个整数n和k。(1 <= n <= 50, 1 <= k <= n) Output 对于每组输入，请输出六行。 第一行： 将n划分成若干正整数之和的划分数。 第二行： 将n划分成k个正整数之和的划分数。 第三行： 将n划分成最大数不超过k的划分数。 第四行： 将n划分成若干奇正整数之和的划分数。 第五行： 将n划分成若干不同整数之和的划分数。 第六行： 打印一个空行。
（ 南开nodgd）： 全是递推题 I: f[i][j]表示i的划分为不超过j个数的划分数，此时分为两种情况： 包括i f[i-j][j]或者不包括i f[i][j-1] II: 初始化：i==1 或者j==1 时f[i][j]=1; 第一个f[i][j]表示i的划分为不超过j个数的划分数，f[i][j]=f[i-j][j]+f[i][j-1]，最终输出f[N][N]。因为这个子问题元素可以多次使用所以递推的时候要用f[i-j][j]这个状态而不能用f[i-j][j-1]。写代码的时候外层循环j由小到大，内层循环i由小到大。 for(j=1;j<=N;j++) f[0][j]=1; for(j=1;j<=N;j++) for(i=j;i<=N;i++) f[i][j]=f[i-j][j]+f[i][j-1]; 一维数组优化： f[0]=1; for(j=1;j<=N;j++) for(i=j;i<=N;i++)//这个顺序每一个数可以取x次 f[i]+=f[i-j]; 第二个f[i][j][k]表示把i划分成不超过j的k个数的划分数，f[i][j][k]=f[i-j][j][k-1]+f[i][j-1][k]，输出f[N][N][K]。这个问题也是可以重复元素的，(如果不允许重复元素就用f[i][j][k]=f[i-j] [j-1][k-1]+f[i][j-1][k])。写代码外层k由小到大，中层j由小到大，内层i由小到大。 for(j=0;j<=N;j++) f[0][j][0]=1; for(k=1;k<=K;k++) for(j=1;j<=N;j++) for(i=j;i<=N;i++) f[i][j][k]=f[i-j][j][k-1]+f[i][j-1][k]; 第三个递推同第一个，输出f[N][K]。 第四个f[i][j]表示把i划分成不超过j的奇数的划分数，f[i][j]=f[i-j][j]+f[i][j-2]，递推循环时保证j是奇数，本质上和第一个相同。如果N是奇数输出f[N][N]，N是偶数输出f[N][N-1]。(如果不允许重复元素就f[i][j]=f[i-j][j-2]+f[i][j-2])，外层循环j由小到大，内层i由小到大。 for(j=1;j<=N;j+=2) f[0][j]=1; for(j=1;j<=N;j+=2) for(i=j;i<=N;i++) f[i][j]=f[i-j][j]+f[i][j-2]; 一维数组优化： f[0]=1; for(j=1;j<=N;j+=2) for(i=1;i<=N;i++) f[i]+=f[i-j]; 第五个f[i][j]表示把i划分为不超过j的不同数的划分数，f[i][j]=f[i-j][j-1]+f[i][j-1]。外层循环j由小到大，内层i由小到大。显然对于每个i的分解，每个j都只被用了一次。 for(j=1;j<=N;j++) f[0][j]=1; for(j=1;j<=N;j++) for(i=j;i<=N;i++) f[i][j]=f[i-j][j-1]+f[i][j-1]; 一维数组优化： f[0]=1; for(j=1;j<=N;j++) for(i=N;i>=j;i--)//这个顺序代表j只能用一次，区分第一个 f[i]+=f[i-j]; 注意： (1)这些实际上都是简单的背包问题的变种，递推方法与背包问题类似。 (2)由于答案可能很大，可能涉及到高精度，但这不影响算法。 (3)以上递推都是最浅显易懂的写法，事实上除第二个以外都可以优化到用一维数组递推(省略[j])，而第二个可以优化到用二维数组递推(省略[k]) 如果还有不能理解的可以草稿纸上写一下或者用程序把递推出的矩阵打出来看一下，应该就能明白了。