题解 | #放苹果#

#include <iostream>
#include <vector>
using namespace std;
  /*
    思路：
    1.边界：0个苹果 1种放法 ；1个苹果 一种放法 ；一个盘子 一种放法
    2.状态转移方程：
        a. 苹果数 > 盘子数(m > n) dp[m][n] 表示m个苹果n个盘子的放法数
            dp[m][n] = dp[m][n-1] + dp[m-n][n]
            分为空一个盘子的放法 + 每个盘子都有苹果的放法
            而每个盘子都放了一个苹果后 等同于 剩余m-n个苹果放盘
        b. 苹果数 <= 盘子数(m <= n) dp[m][n] = dp[m][m];
    */
int main() {
    int m,n;
    cin >> m >> n;
    if(m <= n) n = m;//当盘子数多于苹果数时，多余盘子无作用
    vector<vector<int> > dp(m+1,vector<int>(n+1,0));
   
    for(int i = 0; i <= m; ++i){
        
        for(int j = 0; j <=n; ++j){
            if(i == 0 || i == 1 || j == 1){//边界：0苹果 1苹果 1盘子
                dp[i][j] = 1;
                continue;
            }
            if(i >= j) dp[i][j] = dp[i][j-1] + dp[i-j][j];//放置时苹果多余盘子
            else dp[i][j] = dp[i][i];//放置时苹果少于盘子
        }
    }
    cout << dp[m][n] << endl;
}
// 64 位输出请用 printf("%lld")