最少的硬币数目问题

题目

给定不同面额的硬币 coins 和一个总金额 amount。
编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
你可以认为每种硬币的数量是无限的。

贪心

当给定硬币的币值非常正常的时候我们可以使用贪心算法
例如coins = [1, 2, 5,10,20], amount = 56
我们尽可能多的选择面额大的硬币即可

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        sort(coins.begin(),coins.end());
    	int counts=0;  //用来返回结果
        for(int i=coins.size()-1;i>=0;i--){
        	counts+=amount/coins[i];
        	amount%=coins[i];
        	if(amount==0){
        		return counts;	
        	}
        }
        return -1;	
    }
};

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
 

但是当硬币的面值比较古怪，我们就很可能得不到最优解，甚至等不到答案
比如coins = [2,3,5], amount = 9，很明显得不出答案
再比如coins = [1,2,4,5,6], amount = 9 ，用贪心得出6+2+1 ，但实际上只需要4+5

如何判断硬币的面值能否使用贪心呢？
链接一
链接二

动态规划

开一个数组，保存0~amount的最少硬币数目(比如arr[i]保存的就是amount=i时的最少硬币数目)
所以我们要求的就是arr[amount]

递推公式:
arr[amount]=min(arr[amount-coins[0]], arr[amount-coins[1] ],……, arr[amount-coins[coins.size()-1]])+1
还是很好理解的

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int arr[amount+1];
        arr[0]=0;
        for(int i=1;i<amount+1;i++){
            int min1=1e9;    
            for(int j=0;j<coins.size();j++){
                if(i>=coins[j]){
                    min1=min(min1,arr[i-coins[j]]+1);
                }
            }
            arr[i]=min1;
        }
        if(arr[amount]==1e9){
            return -1;
        }
        return arr[amount];
    }
};

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
 

思考

该题每种硬币的数量是无限的，如果当每种硬币的数目都是有限个c1,c2…cn的时候，如何求解？

当硬币面额可以用贪心时，则可以用贪心来求解。
那用动态规划怎么做呢?
参考1
参考2

文章来源: blog.csdn.net，作者：开心星人，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/qq_55675216/article/details/123927364