整数拆分（动态规划）

整数拆分（动态规划）

题目描述：

给定一个整数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
1
2
3
4
5

输入格式:

每一行输入一组整数n,k，遇到键盘结束符^Z或文件结束符EOF时结束输入。

输出格式:

按行输出每组的拆分方案数。

输入样例:

4,4
5,4
1
2

输出样例:

5
6
1
2

思路：

这道题用动态规划做时间复杂度比较小，定义一个二维数组dp用于存放次数，例如dp[4][3]表示的意思为n=4，k=3，有几种拆分方式，

设f(n,k)为n的k拆分的拆分方案个数：

(1) 当n=1，k=1时，显然f(n,k)=1;

(2) 当n

(3) 当n=k时，其拆分方案有将正整数n无序拆分成最大数为n-1的拆分方案，以及将n拆分成1个n(n=n)的拆分方案，后者仅仅一种，所以有f(n,n)=f(n,n-1)+1

(4) 当n>k时，根据拆分方案中是否包含k，可以分为两种情况：

①拆分中包含k的情况：即一部分为单个k，另外一部分为{X₁,X₂,……X_n}，后者的和为n-k，后者中可能再次出现k，因此是(n-k)的k拆分，所以这种拆分方案个数为f(n-k,k)

②拆分中不包含k的情况：则拆分中所有拆分数都比k小，即n的(k-1)拆分，拆分方案个数为f(n,k-1)因此f(n,k)=f(n-k,k)+f(n,k-1)

样例中如 n=5,k=4，则dp数组为

	J=1	J=2	J=3	J=4	J=5
I=1	1	1	1	1	1
I=2	1	2	2	2	2
I=3	1	2	3	3	3
I=4	1	3	4	5	5
I=5	1	3	5	6	7

代码：

#include
int main()
{
    int n,k;
    int dp[202][202];
    while(~scanf("%d,%d",&n,&k))  //多组输入 
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=k;j++)
            {
                if(i==1||j==1)
                    dp[i][j]=1;
                else if(i==j)
                    dp[i][j]=1+dp[i][j-1];
                else if(i<j)
                    dp[i][j]=dp[i][i];
                else if(i>j)
                    dp[i][j]=dp[i-j][j]+dp[i][j-1];
            }
        }
        printf("%d\n",dp[n][k]);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25