最少的硬币数目问题

文章目录

• • 题目
  • 贪心
  • 动态规划
  • 思考

题目

给定不同面额的硬币 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;    }};

但是当硬币的面值比较古怪，我们就很可能得不到最优解，甚至等不到答案
比如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];    }};

思考

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

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