完全背包板子题
没什么特别的,一个板子,不过要注意开long long
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
long long dp[N];
int main() {
int n, v, coin;
cin >> v >> n;
dp[0] = 1; // 表示单取该货币组成金额j时候的方案数,dp[j] += dp[j - j] (dp[0])
for(int i = 1; i <= v; i++) { // 表示货币种类
cin >> coin;
for(int j = coin; j <= n; j++) { // 至少可以凑出该货币面值的金额,所以可以直接跳过0 ~ coin - 1的循环
dp[j] += dp[j - coin]; // 总方案数不断累加,加上dp[j - coin]状态的方案数
}
}
cout << dp[n] << endl;
return 0;
}