题解 | #放苹果#

以输入(7,3)为例，我们分为有一个盘子没装满和所有盘子至少有一个的情况即(7,2)和(4,3)

这是我们会想，为啥是有一个盘子没装满，两个盘子没装满不行吗？

别急，我们遍历(7,2)时会将其分解为(7,1)和(5,2)，这个(7,1)不就是两个盘子没装满的情况吗

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int f(int m,int n){
    if(m<0||n<0) return 0;
    else if(m==1||n==1) return 1;
    else
        return f(m,n-1)+f(m-n,n);
}
int main() {
    int m,n;
    cin>>m>>n;
    cout<<f(m,n)<<endl;
    return 0;
}
// 64 位输出请用 printf("%lld")

同样我们还可以使用动态规划

#include <iostream>
#include <bits/stdc++.h>
using namespace std;


int main() {
    //注释看题解
    int m,n;
    cin>>m>>n;
    vector<vector<int>>dp(m+1,vector<int>(n+1,0));
    for(int i = 0;i<=m;i++){
        dp[i][1] = 1;//只有一个盘子
    }
    for(int j = 1;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][j]+dp[i][j-1];
            }
        }
    }
    cout<<dp[m][n]<<endl;
    return 0;
}