题解 | #放苹果#

#include <iostream>
using namespace std;
#include <vector>
int main() {
    int m, n;
    cin >> m >> n;
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    //dp数组，dp[i][j]表示 i个苹果放在j个盘子里有几种放法

    //初始化dp数组,1个盘子不论多少苹果都只有1种放法
    for (int i = 1; i <= m ; i++) {
        dp[i][1] = 1;
    }

    //初始化dp数组，，这种特殊情况值要给1，其实可以不用理解为0个苹果j个盘子有1种放法。
    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 (j > i) {
                //如果盘子数已经大于苹果数，那怎么加盘子放法都固定
                dp[i][j] = dp[i][i];
            }
            else{
                dp[i][j] = dp[i -j][j] + dp[i][j - 1];//有盘子空着，即为dp[i][j-1],无盘子空着即为dp[i-j][j]
            }
        }
    }
    cout << dp[m][n] << endl;

}

动态规划不太好理解，主要是苹果数大于等于盘子数时，需要将有盘子空着与无盘子空着2种情况相加

dp[i-j]就是将苹果在每个盘子都放一个，之后剩下的苹果的所有情况,也就是无盘子空着的情况

如果i == j,也就是dp[0][j]，这个需要初始化，苹果盘子数目相等，又要没有空盘子，所有这种特殊情况值要给1，其实可以不用理解为0个苹果j个盘子有1种放法。