动态规划

#include <iostream>
#include <vector>
using namespace std;

int divideNumber(int n, int k) {
    // dp[i][j]表示将i分成j份的分法数
    vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));
    
    // 初始化基础情况
    for (int i = 1; i <= n; ++i) {
        dp[i][1] = 1; // 任何数分成1份只有1种分法
    }
    
    for (int i = 2; i <= n; ++i) {
        for (int j = 2; j <= k; ++j) {
            if (i >= j) {
                // 两种情况相加：
                // 1. 至少有一个1的分法（相当于dp[i-1][j-1]）
                // 2. 所有数都大于1的分法（相当于dp[i-j][j]）
                dp[i][j] = dp[i-1][j-1] + dp[i-j][j];
            } else {
                dp[i][j] = 0; // 无法将i分成j份
            }
        }
    }
    
    return dp[n][k];
}

int main() {
    int n, k;
    cin >> n >> k;
    cout << divideNumber(n, k) << endl;
    return 0;
}