2139: 信息学奥赛一本通T1291-数字组合 两种方法超简单

解题思路:

注意事项:

参考代码:

DFS

#include"bits/stdc++.h"
using namespace std;
// 全局变量声明
int n, t, a[25]; // n: 数组大小，t: 目标和，a: 存储输入的数组
int kkk = 0; // 计数器，记录满足条件的组合数
void dfs(int x, int sum) {
    // 如果当前组合的和大于目标值，则返回
    if (sum > t) return;
    // 如果当前组合的和等于目标值，则计数器加1
    if (sum == t) {
        kkk++;
        return;
    }
    // 遍历从当前索引到数组末尾的所有元素
    for (int i = x; i <= n; i++) {
        // 递归调用dfs函数，处理下一个元素
        dfs(i + 1, sum + a[i]);
    }
}
int main() {
    // 读取输入的n和t
    cin >> n >> t;
    // 读取数组a的元素
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    // 调用dfs函数，从第一个元素开始，初始和为0
    dfs(1, 0);
    // 输出满足条件的组合数
    cout << kkk << endl;
    return 0;
}

DP

#include"bits/stdc++.h"
using namespace std;
// 定义全局变量n, t和数组a, dp
int n,t,a[25],dp[1100];
int main(){
    // 读取输入的n和t的值
    cin>>n>>t;
    // 读取n个整数并存储到数组a中
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    // 初始化dp数组，dp[0]设为1表示目标和为0时有一种方案
    dp[0]=1;
    // 动态规划计算组合数
    for(int i=1;i<=n;i++){
        for(int j=t;j>=a[i];j--){
            // 更新dp数组，当前状态由前一个状态转移而来
            dp[j]=dp[j]+dp[j-a[i]];
        }
    }
    // 输出结果，即达到目标和t的组合数
    cout<<dp[t]<<endl;
    return 0;
}