题解|《信息学奥赛一本通》 数的划分

题目描述
将整数n分成k份，且每份不能为空，问有多少种不同的分法。当n=7,k=3时，下面三种分法被认为是相同的：1,1,5;1,5,1;5,1,1

输入描述:
一行两个数n,k。

输出描述:
一行一个整数，即不同的分法数。

思路：
dp[n][k] 表示 n 分成 k 个非空的数的方案数。
显然 n<k 时 dp[n][k]=0 , n=k 时 dp[n][k]=1;
其他的可以分情况讨论：
1.有1的
2.没1的
第一种情况，方案数为 dp[n-1][k-1]
第二种情况，方案数为 dp[n-k][k] (此时 n 必须大于 k)

so，可以转换为：dp[n][k]=dp[n-1][k-1]+dp[n-k][k]。

dp版AC代码：

#include <iostream>
#include <algorithm>

using namespace std;

int dp[205][10];

int main() {
    ios::sync_with_stdio(false);

    int n, k;
    cin >> n >> k;

    dp[0][0] = 1;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= min(i, k); j++) {
            dp[i][j] = dp[i - 1][j - 1] + dp[i - j][j];
        }
    }

    cout << dp[n][k] << endl;

    return 0;
}