完全背包问题方案数
ref{:target=”_blank”}
问题转化:
将总的 amount -》背包体积
coin -》物品
coin的面额 -》物品体积
求方案数,递进关系是 f[j] += f[j-v[i]]; 即在之前方案数的基础上,添加 v[i] 形成新的方案。
C++ 代码
class Solution {
public:
int change(int amount, vector<int>& coins) {
int n = coins.size();
vector<int> f(amount+1);
f[0] = 1;
for(int i=1; i<=n; ++i) {
for(int j=0; j<=amount; ++j) {
if(j >= coins[i-1]) {
f[j] += f[j-coins[i-1]];
}
}
}
return f[amount];
}
};
二维空间版本
class Solution {
public:
int change(int amount, vector<int>& coins) {
int n = coins.size(), m = amount;
vector<vector<int>> f(n+1, vector<int>(m+1));
f[0][0] = 1;
for(int i=1; i<=n; ++i) {
for(int j=0; j<=m; ++j) {
f[i][j] = f[i-1][j];
if(j>=coins[i-1]) {
f[i][j] += f[i][j-coins[i-1]];
}
}
}
return f[n][m];
}
};