题解 | #神奇的口袋#

写题思路 ： 这题 两种方法 动规 和 回溯 都能做

动规的话 看题目问 有多少种方式 这种一眼组合数的dp板子

核心状态转移方程：dp[j] += dp[j - goods[i]];

然后dp[0]初始化为1

然后一维滚动数组 遍历背包时 要从末尾开始

这个地方建议多看看 carl哥的归纳总结 还是很细致的

回溯的话 其实就是dfs 暴力搜寻 满足题目条件就加一 注意剪枝优化即可

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

int n;
vector<int> goods;

int main() {
    cin >> n;
    while (n--) { // 注意 while 处理多个 case
        int num;
        cin >> num;
        goods.push_back(num);
    }
    int dp[40 + 10];
    memset(dp, 0, sizeof(dp));
    dp[goods[0]] = 1;
    dp[0] = 1; //组合数 0要初始为1  做题经验吧
    for(int i = 1; i < goods.size(); i++){
        for(int j = 40; j >= goods[i]; j--){
              dp[j] += dp[j - goods[i]]; //组合数套公式是吧
        }
    }
    cout << dp[40];
}
// 64 位输出请用 printf("%lld")