题解 | 放苹果

#include <iostream>
#include <cstring> // 用于memset

using namespace std;

int dp[11][11]; // 全局记忆数组，m和n最大为10

int f(int m, int n) {
    if (m == 0) return 1; // 没有苹果，只有一种分法
    if (n == 0) return 0; // 没有盘子，无法分
    if (dp[m][n] != -1) return dp[m][n]; // 已计算过，直接返回

    //3种边界情况处理

    int res = f(m, n - 1); // 至少有一个空盘的情况
    if (m >= n) {
        res += f(m - n, n); // 所有盘子至少有一个苹果的情况
    }
    dp[m][n] = res; // 记录结果
    return res;
}

int main() {
    int M, N;
    while (cin >> M >> N) {
        memset(dp, -1, sizeof(dp)); // 每次计算前重置记忆数组
        cout << f(M, N) << endl;
    }
    return 0;
}