LeetCode 322. Coin Change

[Woodyiiiiiii]

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:

Input: coins = [1, 2, 5], amount = 11
Output: 3 
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

Note:
You may assume that you have an infinite number of each kind of coin.

---

dp一维数组每个元素代表达到金钱i所需要的最少硬币数，根据之前空间的数据递归求解。

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        int i = 0;
        int j = 0;
        for (i = 0; i <= amount; ++i) {
            dp[i] = amount + 1;
        }
        dp[0] = 0;
        
        for (i = 0; i <= amount; ++i) {
            for (j = 0; j < coins.length; ++j) {
                // if (i - coins[j] >= 0)
                if (coins[j] <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        
        return (dp[amount] > amount) ? -1 : dp[amount];
    }
}

func coinChange(coins []int, amount int) int {
	dp := make([]int, amount+1)
	dp[0] = 0
	for i := 1; i <= amount; i++ {
		dp[i] = amount + 1
		for _, coin := range coins {
			if i-coin >= 0 && dp[i-coin] != amount+1 {
				dp[i] = int(math.Min((float64)(dp[i-coin]+1), (float64)(dp[i])))
			}
		}
	}
	if dp[amount] == amount+1 {
		return -1
	}
	return dp[amount]
}

我自己写了一个用二维数组的dp解法，行i代表硬币下标，列j代表总钱数，元素代表在用了coins[i]之前的硬币所能达到j的最少货币数，然而有个corn case，-1与0如何区分？所以并没有accepted，以后可以完善下。

class Solution {
    public int coinChange(int[] coins, int amount) {
        int len = coins.length;
        int[][] dp = new int[len][amount + 1];
        int i = 0, j = 0, k = 0;
        int res = Integer.MAX_VALUE;
        for (i = 0; i < len; ++i) {
            for (j = 0; j <= amount; ++j) {
                dp[i][j] = -1;
            }
        }
        for (i = 0; i * coins[0] <= amount; ++i) {
            dp[0][i * coins[0]] = i;
        }
        
        for (i = 1; i < len; ++i) {
            for (j = 0; j <= amount; ++j) {
                dp[i][j] = dp[i - 1][j];
                for (k = 1; j - k * coins[i] >= 0; ++k) {
                    if (dp[i][j] != -1 && dp[i - 1][j - k * coins[i]] + k != -1)
                        dp[i][j] = Math.min(dp[i - 1][j - k * coins[i]] + k, dp[i][j]);
                }
            }
        }
        
        for (i = 0; i < len; ++i) {
            if (dp[i][amount] != -1)
                res = Math.min(dp[i][amount], res);
        }
        if (res == Integer.MAX_VALUE) return -1;
        return res; 
    }
}

然而创建二维dp数组的做法不建议，因为硬币可以任意选任何一个，dp[i][j] = Math.min(dp[i - 1][j - k * coins[i]] + k, dp[i][j])无法成立。

类似的题目可以在《程序员代码面试指南》找到。

这种硬币系列分为两种：①最少货币数(Min Path)；②多少种方法(Distinct way)。
这两种都是可以用一维dp数组来做。

---

参考资料:

1. LeeteCode原题
2. grandyang