给定一个整数n，将其无序拆分成最大数为k的拆分数，（n,k不超出100） 要求：所有的拆分方案不重复。 如当n=4,k=4时，一共有5种拆分方案，拆分如下：
(1)4=1+1+1+1 (2)4=1+1+2 (3)4=1+3 (4)4=2+2 (5)4=4
输入格式:
每一行输入一组整数n,k，遇到键盘结束符^Z或文件结束符EOF时结束输入。
输出格式:
按行输出每组的拆分方案数。
输入样例:
4,4 5,4
输出样例:
5 6
程序中的df[n][k]的值就是用户输入n,k，后要输出的值 程序的关键是怎么让后面的元素用前面的元素表示出来 把题目用(n,k)=c来表示，再把k大于n的情况考虑进去，会得到下表 (1,1)=1 (1,2)=1 (1,3)=1 (1,4)=1 (2,1)=1 (2,2)=2 (2,3)=2 (2,4)=2 (3,1)=1 (3,2)=2 (3,3)=3 (3,4)=3 (4,1)=1 (4,2)=3 (4,3)=4 (4,4)=5 (5,1)=1 (5,2)=3 (5,3)=5 (5,4)=6 从中找规律，让后面的元素用前面的元素表示 可以得到规律如下： 当k=1时，(n,k)=1,这些就是最基础的元素了 当k>n时，(n,k)=(n,k-1) 当k<n时，(n,k)=(n,k-1)+(n-k,k) 当k=n是，(n,k)=(n,k-1)+1
#include<iostream> #include<stdio.h> int N[100][100]; int main(){ int n,k; while(scanf("%d,%d",&n,&k)!=EOF){ //遇到键盘结束符^Z或文件结束符EOF时结束输入。或~scanf for(int i=1;i<=n;i++){ //循环从1开始~ for(int j=1;j<=k;j++){ //当n==1时，无论k为何值，都只有一种拆分方案。即{1}。 //当k==1时，无论n为何值，都只有一种拆分方案。即{1，1，……，1，1}。因为拆分的最大数不能超过k，所以只能拆成1。 if(i==1||j==1){ N[i][j]=1; } //当n==k时 //根据拆分出来的数是否包含n，可以分成两种情况。 //拆分出来的整数包含n，那就只有一种情况，即{n}。 //拆分出来的整数不包含n，那么这些拆分出来的数中，一定比n小，即n的所有（n-1）拆分。因此dp[n][k]=1+dp[n][k-1]; else if(i==j){ N[i][j]=N[i][j-1]+1; } //当n<k时 //因为拆分出来的最大数永远不可能达到k。所以等价于n的所有n拆分。因此dp[n][k]=dp[n][n]; else if(i<j){ N[i][j]=N[i][i]; } //当n>k时 //根据拆分出来的整数中是否包含k，可以分为两种情况： //拆分出来的整数中包含k，即{k,{a1,a2,……，ai}),其中{a1,a2,……，ai}的和为n-k， //可能再次出现k，因此是（n-k）的k拆分。因此这种情况的拆分数是dp[n-k][k]。 //拆分出来的整数中不包含k的情况，则拆分出来的整数中所有值都比k小，即n的（k-1）划分。拆分数为dp[n][k-1]。 //所以dp[n][k]=dp[n-k][k]+dp[n][k-1]。 else if(i>j){ N[i][j]=N[i][j-1]+N[i-j][j]; } } } printf("%d\n",N[n][k]); } }