参考文献
完全背包问题
ref{:target=”_blank”}
C++ 代码
class Solution {
public:
// 完全背包问题,每个物品的体积是coin,价值是1,求amount体积的最小价值
// f[i][j] 表示使用前i个coin, j 价值下,最少需要的coin数量, i维度可以优化
int coinChange(vector<int>& coins, int amount) {
const int INF = 1e8;
vector<int> f(amount+1, INF);
// 初始化
f[0] = 0;
for(int i=0; i<coins.size(); ++i){
for(int j=coins[i]; j<=amount; ++j){
f[j] = min(f[j], f[j-coins[i]]+1);
}
}
int res = f[amount] == INF ? -1 : f[amount];
return res;
}
};