题解 | #放苹果#

#include <iostream>
using namespace std;
// 实际上可以等效为组合问题：从[0,m]中选择3个值，使和为m
// 由于可以重复，因此下一层的start可以等于本层的i
int ways=0;
void traceback(int m,int n,int sum,int start){
    if(n==0){
        if(sum==m)
            ++ways;
        return;
    }
    for(int i=start;i<=m-sum;++i){
        sum+=i;
        traceback(m,n-1,sum,i);
        sum-=i;
    }
}

int main() {
    int m,n;
    cin >> m >> n;
    traceback(m,n,0,0);
    cout << ways;
}
// 64 位输出请用 printf("%lld")

#include <iostream>
using namespace std;
// 发现规律，令(m,n)为m个球放到n个盘子中的方法数
// m个球放到n个盘子中
// 有一个盘子没有放球，其余盘子随意，方式数目为(m,n-1)
// 所有盘子都至少一个球，剩余球随意，方式数目为(m-n,n)
int digui(int m,int n){
    if(m<0||n<0)
        return 0;
    if(m==1||n==1)
        return 1;
    return digui(m,n-1)+digui(m-n,n);
}

int main() {
    int m,n;
    cin >> m >> n;
    cout << digui(m,n);

}
// 64 位输出请用 printf("%lld")

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

// 设置动态规划数组 dp[i][j]为j个球放到i个盘子的方法
// 递推式：dp[i][j]=dp[i-1][j]+(j<i?0:dp[i][j-1]);
// 边界条件：dp[i][0]=dp[i][1]=1 dp[1][i]=1
// 易错点：递推式中，将所有盘子至少一个球这一项（(j<i?0:dp[i][j-1])）需要单独加括号，提高优先级

int main() {
    int m,n;
    cin >> m >> n;
    vector<vector<int>> dp(n+1,vector<int>(m+1,1));
    for(int i=0;i<=n;++i){
        dp[i][0]=1;dp[i][1]=1;
    }
    for(int i=2;i<=n;++i){
        for(int j=2;j<=m;++j){
            dp[i][j]=dp[i-1][j]+(j<i?0:dp[i][j-i]);
        }
    }
    cout << dp[n][m];
}
// 64 位输出请用 printf("%lld")