零钱兑换(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];}
};
更多推荐
[贪心法+回溯法][完全背包]leetcode322:零钱兑换(medium)
发布评论