递归+记忆化
记忆数组两维,第一维度表示第几枚硬币,第二维度表示总共钱数。
注意:要用long long
这里debug好久。
#include <algorithm>
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
long long vec[26];
long long dp[26][10001];
long long v, n;
long long dfs(int i, int j) {
// 不能写在这里!过不了 25 1000 这个案例
// if (dp[i][j] != -1) {
// return dp[i][j];
// }
if (i == v) {
return 0;
}
if (j < 0) {
return 0;
}
if (j == 0) {
return 1;
}
if (dp[i][j] != -1) {
return dp[i][j];
}
long long cnt = 0;
cnt += dfs(i, j - vec[i]);
cnt += dfs(i + 1, j);
dp[i][j] = cnt;
return dp[i][j];
}
int main() {
memset(dp, -1, sizeof(dp));
while (cin >> v >> n) {
for (int i = 0; i < v; ++i) {
cin >> vec[i];
}
cout << dfs(0, n) << endl;
}
return 0;
}