LC 322 Coin Change(M)

You are given coins of different denominations and a total amount of moneyamount. 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.

public int coinChange(int[] coins, int amount) {

解题思路：DP, Memorize

边界条件：如果amount < 1返回0；

迭代解法：从1到amount,求解每个最少的coin组合，保存下来，当大amount- coin等于数组中的值时候，大amount的最新coin值就是数组中的值加一，但要比较那个是最小组合。采用的是从底到上的方法。

For the iterative solution, we think in bottom-up manner. Suppose we have already computed all the minimum counts up tosum, what would be the minimum count forsum+1?

public int coinChange(int[] coins, int amount) { 
    if(amount<1) return 0; 
    int[] dp = new int[amount+1]; // 记录 1 到 amount的最小组合 
    int sum = 0; 

    while(++sum<=amount) { 
        int min = -1; // 如果没有coin组合，维持 -1 
        for(int coin : coins) { //每个coin和sum比较 
            if(sum >= coin && dp[sum-coin]!=-1) { //只有sum大于等于coin的值 并且 sum – coin 是有coin组合的 
                int temp = dp[sum-coin]+1;  // 当前临时组合值是  
                //如果 min还是初始-1. Temp 就是当前最小，否则比取temp 和 min中的最小值 
                min = min<0 ? temp : (temp < min ? temp : min);      
            } 
        } 
        dp[sum] = min; // 保留当前sum的最小coin组合 
    } 
    return dp[amount]; 
}

递归解法：考虑最后一步，如果我们已经知道组合amount的最好方法，最后一步是我们取任意coin给我们一个剩余r (r=amount –coin[i]),对所有remainder做同样的操作，直到结果要么是0或小于0(代表无效),过程中要保留以及算过的最小coin组合值。

public int coinChange(int[] coins, int amount) { 
    if(amount<1) return 0; 
    return helper(coins, amount, new int[amount]); 
} 
// rem: remaining coins after the last step; count[rem]: minimum number of coins to sum up to rem 
private int helper(int[] coins, int rem, int[] count) {      
    if(rem<0) return -1; // 如果剩余小于0，表示这种组合不正确 
    if(rem==0) return 0; // 真好为0，表示这种组合可以是一种候选 
    if(count[rem-1] != 0) return count[rem-1]; // 如果已经计算，直接返回。因为 count数组是 0 到 amount - 1 
    int min = Integer.MAX_VALUE; 
    for(int coin : coins) { 
        int res = helper(coins, rem-coin, count); // 求解 rem-coin的coin组合值， 
        if(res>=0 && res < min) //如果有(>0) 并且小于当前 min 更新 min = res + 1 
            min = 1+res;  
    } 
    count[rem-1] = (min==Integer.MAX_VALUE) ? -1 : min; // 记录当前rem 的最小coin组合值。 
    return count[rem-1]; 
}