You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)
Example 2:
coins = [2], amount = 3
return -1.
Note:
You may assume that you have an infinite number of each kind of coin.
分析：题意为给你不同面值的硬币和总金额数，写一个函数去计算构成这个总金额所需的最小的硬币数目。如果硬币的任何组合都不能构成总钱数就返回-1。
思路：很明显的DP问题，一开始在想是否可以使用贪心算法，发现这样是不能保证最小coin数目的，例如：amount = 8, coins为[1, 3, 5, 6]，采用贪心策略得到3（6，1，1），而实际上正确值为2（5，3），之所以贪心法在这里不适用是因为贪心所作的决策并不能确保全局最优，如果换作问题为提水，每桶都有一定量的水，怎样才能最少次数运完所有的水，这样可以用贪心选择最多的水，因为每次提越多的水，到最后的次数肯定最少。
本题两种解决办法，但是思想是一样的：
1、使用线性规划法，dp[n]为amount为n的change数目，那么我们从dp[1]开始就可以DP到dp[n]，迭代关系式为，dp[n] = min(dp[n], dp[n-coins[m]]+1).
2、使用递归的方法，不过有可能会造成memory exceed，递推关系为count(n,m,coins) = min(count(n,m-1,coins), count(n-coins[m],m,coins)); 其中count表示寻找最少change的函数，n为amount，m为coins（排好序的）的下标。
代码：
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
if(!coins.size() && amount)
return -1;
vector<int> dp(amount + 1, INT_MAX);
dp[0] = 0;
for (auto coin : coins) {
for (int i = coin; i <= amount; ++i) {
if (dp[i-coin] != INT_MAX) {
dp[i] = min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] == INT_MAX?-1:dp[amount];
}
};
参考方法2：the first recursive DFS solution
Just use the array to record the previous computed states.
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
if(amount<1) return 0;
vector<int> dp(amount, 0);
return help(coins, amount, dp);
}
int help(vector<int>& coins, int remain, vector<int>& dp){
if(remain<0) return -1;
if(remain==0) return 0;
if(dp[remain-1]!=0) return dp[remain-1];
int min=INT_MAX;
for(int coin : coins){
int result=help(coins, remain-coin, dp);
if(result>=0 && result<min)
min=1+result;
}
dp[remain-1]=(min==INT_MAX ? -1 : min);
return dp[remain-1];
}
};