[基础dp]Aizu - ALDS1_5_A-Exhaustive Search

https://vjudge.net/problem/Aizu-ALDS1_5_A

蒟蒻开始接触dp了 第一道dp好像很简单

题意：给定一个数组 问选任意个元素是否能够凑出所给的数字 如果可以 输出yes 否则输出no

思路：就是对于每个元素 有选或者不选两种选择 直到选的个数超过了最大个数（失败）或者所选元素之和刚刚好就是所求的数字（成功）

#include
#include
#include
#include
#include
#include
#include
#include
#include

int solve(int i, int m) {
if (m == 0) {//剩余量为0
return 1;//解决问题
}
else if (i >= n) {//用的元素个数超过了n
return 0;
}
return solve(i + 1, m) + solve(i + 1, m - arr[i]);//递归 选用当前元素或者不选用当前元素
}

int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
int m, t;
cin >> m;
for (int i = 0; i < m; i++) {
cin >> t;
if (solve(0, t)) {
cout << “yes” << endl;
}
else {
cout << “no” << endl;
}
}
return 0;
}