[贪心法+回溯法][完全背包]leetcode322：零钱兑换(medium)

零钱兑换(medium)"/>

[贪心法+回溯法][完全背包]leetcode322：零钱兑换(medium)

题目：

题解：

思路1：贪心+回溯

• 贪心：将零钱由大到小排序，便于首先选择面值较大的零钱。
• 回溯：若某个零钱选择之后，它后面的小零钱不能完成兑换的话，我们需要回溯，也就是将面值较大的零钱减少一张。
• 加速 or 剪枝：每次直接将面值大的零钱选用最大张数，加速零钱兑换；若可兑换的零钱数大于 res 了，那么我们应该剪枝，也就是将将面值较大的零钱减少一张。

---

思路2：完全背包板子

• 思路直接看代码即可。

代码如下：

class Solution {
public:int coinChange(vector<int>& coins, int amount) {if(!amount)return 0;int res=INT_MAX;sort(coins.rbegin(),coins.rend());//由大到小排序，便于贪心地选取面值大的零钱dfs(coins,amount,0,0,res);return res==INT_MAX?-1:res;}//回溯寻找满足情况的最少零钱数，k表示一次可拿coins[i]的最大次数，若后面不能达到零钱完全兑换或者兑换的零钱数大于res时，用来回溯k--或剪枝//index用来遍历coins，count用来统计已用的零钱数void dfs(vector<int>& coins,int amount,int count,int index,int& res){if(amount==0){res=min(res,count);return;}if(index==coins.size())return;for(int k=amount/coins[index];k>=0&&k+count<res;--k){//k用来枚举所有零钱兑换的状态的dfs(coins,amount-k*coins[index],count+k,index+1,res);}}
};

// 思路2 完全背包板子
const int M = 20,N = 1e4+10;
const int INF = 0x3f3f3f3f;
int f[M][N];// 状态 f[i][j] 表示从前i个物品(物品0不存在)种选，且总体积恰好为j的物品最少数量
class Solution {
public:// 完全背包问题int coinChange(vector<int>& v, int n) {// 初始值设为无效值--无穷，因为要求总体积恰好为n的最少物品数量memset(f,0x3f,sizeof f);// 选取0个物品且总体积为0的最少物品数量为0f[0][0]=0;// 表示有m个物品int m=v.size();for(int i=1;i<=m;++i)for(int j=0;j<=n;++j){// 不选物品i且总体积为j的最少物品数f[i][j]=f[i-1][j];if(j>=v[i-1])f[i][j]=min(f[i][j],f[i][j-v[i-1]]+1);}return f[m][n]==INF?-1:f[m][n];}
};