易懂带注释题解

题意

题目要计算在盘子里放苹果各种放法的方法数。

解析

本题需要使用递归，用来枚举每个盘子中的苹果个数，因此递归层数就是盘子总数。一旦每个盘子都枚举完，即可判断苹果总数是否与m的值相等，是的话计数变量自增。

标程

#include<bits/stdc++.h>
using namespace std;
int t;
int m, n, num[30], ans;
void dfs(int x){
    if(x == n + 1){
        int sum = 0;
        for(int i = 1; i <= n; i++){
            sum += num[i];//计算苹果总数
        }
        if(sum == m){//判断是否正好放完
            ans++;
        }
        return;//枚举下一种放法
    }
    for(int i = num[x - 1]; i <= m; i++){//i的下界为num[x - 1]，是为了去重
        num[x] = i;//记录当前放的数量
        dfs(x + 1);//枚举下一个盘子
    }
}
int main(){
    cin >> t;
    for(int i = 1; i <= t; i++){
        cin >> m >> n;
        ans = 0;
        dfs(1);
        cout << ans << endl;//输出此次放法数
    }
    return 0;
}

本题亦可进行如下优化：

#include<bits/stdc++.h>
using namespace std;
int t;
int m, n, num[30], ans, sum;
void dfs(int x){
    if(x == n + 1){
        if(sum == m){//此时不再需要对sum进行for循环累加赋值，直接用即可
            ans++;
        }
        return;
    }
    for(int i = num[x - 1]; i + sum <= m; i++){//加入关于当前苹果数sum加上准备进行放入的苹果数是否不超过m的判断，使得排除一些不满足条件的放法
        num[x] = i;
        sum += i;//更新苹果总数
        dfs(x + 1);
        sum -= i;//回溯
    }
}
int main(){
    cin >> t;
    for(int i = 1; i <= t; i++){
        cin >> m >> n;
        ans = 0;
        dfs(1);
        cout << ans << endl;
    }
    return 0;
}

后记

优化在于：给每个盘子放入苹果前，先判断是否有足够苹果进行放入。并且在枚举好当前盘子后，直接更新苹果总数sum，使得在验证过程中不再需要对其进行修改。

本题解在核桃oj上也有发布，均为本人所著。