leetcode-322 零钱兑换--完全背包问题
本题是一个完全背包问题，使用优化为O(UV)的算法
完全背包问题：
有 N 种物品和一个容量为 V 的背包，每种物品都有无限件可用。放入第 i 种物品 的费用是 Ci，价值是 Wi。求解：将哪些物品装入背包，可使这些物品的耗费的费用总 和不超过背包容量，且价值总和最大。
令 F[i,v] 表示前 i 种物品恰放入一个容量为 v 的背包的最大权值。可以按照每种物品不同的策略写出状态转移方程(优化后)：F[i,v] = max(F[i − 1,v], F[i,v − Ci] + Wi)优化空间后：
F[v] ← max(F[v],F[v − Ci] + Wi)
算法伪代码：
F[0..V ]←0 for i ← 1 to N for v ← Ci to V F[v] ← max(F[v],F[v − Ci] + Wi)
于是本题：
for i ← 1 to coins.size() for j ← C[i] to amount F[j] ← min(F[j],F[j − C[i]] + 1本题解答：
int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount+1,INT_MAX-1);
dp[0]=0;
for(int i=0;i<coins.size();i++)
for(int j=coins[i];j<=amount;j++){
dp[j]=min(dp[j],dp[j-coins[i]]+1);
}
return dp[amount]<INT_MAX-1?dp[amount]:-1;
}
查看15道真题和解析