题目

题目描述

将整数n分成k份，且每份不能为空，任意两种划分方案不能相同(不考虑顺序)。 
例如：n=7，k=3，下面三种划分方案被认为是相同的。 
1 1 5 
1 5 1 
5 1 1 
问有多少种不同的分法。

输入描述

输入：n，k (6

输出描述

输出：一个整数，即不同的分法。

样例输入

7 3

样例输出

4

题解！

我们用dp[i][j]表示把数字i分成j份的方案数，那么： 
1. i < j 时，不存在方案，dp[i][j]=0; 
2. i >= j 时，考虑： 
    1) 当前方案存在“1”这个数时，可以“裁去”这个1，从而实现 j 的减少。 
 
    2) 当前方案不存在“1”这个数时，j减少不了，但是仍可以“裁去”最底下的“一层”，即所有数减去1，总数i减去j，实现 i 的减少。 

所以： 

 dp[i][j]=dp[i-1][j-1]+dp[i-j][j];(j<=i)

代码：

 1 #include <cstdio> 2 using namespace std; 3 int N, K, dp[205][8]; 4 int main(){ 5 scanf("%d%d", &N, &K); 6 dp[0][0] = 1; 7 for(int i = 0; i <= N; i++) 8 for(int j = 1; j <= K && j <= i; j++) 9 dp[i][j] = dp[i-1][j-1] + dp[i-j][j];10 printf("%d\n", dp[N][K]);11 return 0;12 }

CodeVS1039 数的划分 插图题解！