题解 | #放苹果#

使用动态规划思想求解，即 dp[i][j] 表示将 i 个苹果放入到 j 个盘子的方法总数。

1. 若 i<j，即苹果比盘子数小
   • 比如将 2 个苹果放入 3 个盘子，必然会有一个盘子为空，即{0,x,y}，其中一位固定为 0，不会影响最终的方案数，这和将 2 个苹果放入 2 个盘子的方案数目是一样的，即 {x,y}
   • 因此有当 i<j 时，dp[i][j] = dp[i][i]
2. 若 i>=j，即苹果数目不小于盘子数时，考虑是否有空盘子的情况（比如将 4 个苹果放入 3 个盘子）
   • 若有空盘情况，相当于盘子数量少一个（因为固定一位是空盘，不会影响最终方案数目），即 {x,y,0}，这对应着 dp[i][j-1]
   • 若没有空盘的情况，对于 j 个盘子，相当于拿出来 j 个苹果，分配到每个盘子中1个，保证每个盘子分配到一个苹果。然后将剩下的 i-j 个苹果再分到 j 个盘子里，这对应着 dp[i−j][j]
   • 因此有当 i>=j 时，dp[i][j] = dp[i][j-1] + dp[i−j][j]
3. 边界条件
   • 对于只有 1 个盘子的情况，分配方案只有 1 种，dp[i][1] = 1;
   • 对于只有 0 个苹果的情况，分配方案只有 1 种，dp[0][j] = 1;
   • 对于只有 1 个苹果的情况，分配方案只有 1 种，dp[1][j] = 1;

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

int main(){
    int m;
    int n;
    while (cin >> m) {
        cin >> n;
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        if (m == 0 || m == 1 || n == 1) {
            cout << 1;
            break;
        }
        // 边界条件
        for (int i = 0 ; i <= m; i++) {
            dp[i][1] = 1;
        }
        for (int j = 0 ; j <= n; j++) {
            dp[0][j] = 1;
            dp[1][j] = 1;
        }
        
        for (int i = 2; i <= m; i++) {
            for (int j = 2; j <= n; j++) {
                if (i < j) {
                    dp[i][j] = dp[i][i];
                } else {
                    dp[i][j] = dp[i][j - 1] + dp[i - j][j];
                }
            } 
        }
        cout << dp[m][n] <<endl;
    }
}