CodeVS1039 数的划分 插图题解！

题解

题目

题目描述

将整数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 的减少。

所以：

代码：

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

蒟蒻一棵↓，欢迎批评指正！

作者：胡小兔
联系：yuanxiaodidl@163.com
Q Q ：939480516