https://www.nowcoder.com/practice/bfd8234bb5e84be0b493656e390bdebf?tpId=37&tqId=21284&ru=/exam/oj

  1. 如果 n > m，将 n 设置为 m。
  2. 初始化一个数组 dp，其中 dp[i][j] 表示将 i 个苹果放入 j 个盘子中的不同分法数量。数组的大小应该是 (m+1) x (n+1)。
  3. 使用两个嵌套循环来遍历所有可能的苹果数量和盘子数量。对于每个 i 和 j，计算 dp[i][j] 如下：
    • 如果 i == 0 或 j == 1，则 dp[i][j] = 1（只有一种方法：所有盘子都是空的，或者所有苹果都放在一个盘子里）。
    • 否则，如果 i < j，则 dp[i][j] = dp[i][i]（因为至少有 j - i 个盘子是空的）。
    • 否则，dp[i][j] = dp[i-j][j] + dp[i][j-1]（事件A:要么每个盘子都至少放一个苹果，事件B:要么至少有一个盘子是空的，A与B是互斥事件，A∩B=空集，A∪B=全集）。但是，由于我们不允许有区别的盘子，我们需要确保 dp[i-j][j] 是按非递增顺序计算的。这可以通过在内部循环中添加一个条件来实现。
  4. 返回 dp[m][n] 作为结果。
#include <bits/stdc++.h>
using namespace std;

int countWays(int m, int n) {
    // 如果盘子多于苹果，则多余的盘子不会有苹果
    if (n > m) {
        n = m;
    }

    // 创建一个动态规划表，dp[i][j]表示将i个苹果放入j个盘子中的分法数量
    std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));

    // 初始化边界条件
    for (int i = 0; i <= m; ++i) {
        dp[i][0] = 0; // 没有盘子时，分法数量为0
    }
    for (int j = 1; j <= n; ++j) {
        dp[0][j] = 1; // 没有苹果时，只有一种分法（所有盘子都是空的）
    }

    // 填充动态规划表
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            // 如果苹果数量小于盘子数量，则只考虑苹果数量的盘子
            if (i < j) {
                dp[i][j] = dp[i][i];
            } else {
                // 否则，考虑两种情况：所有盘子都至少有一个苹果，或者至少有一个盘子是空的
                dp[i][j] = dp[i - j][j] + dp[i][j - 1];
            }
        }
    }

    // 返回结果
    return dp[m][n];
}

int main() {
    int m, n;
    while (cin >> m >> n) { // 注意 while 处理多个 case
        cout << countWays(m, n) << endl;
    }
}