322 Coin Change

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：

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

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

Note：

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

解释下题目：

1. 动态规划

实际耗时：xxms

public int coinChange(int[] coins, int amount) {
    if (amount < 1) {
        return 0;
    }
    int[] dp = new int[amount];
    return helper(coins, amount, dp);
    //System.out.println(Arrays.toString(dp));
}

private int helper(int[] coins, int left, int[] dp) {
    if (left < 0) {
        return -1;
    }
    if (left == 0) {
        //found the answer
        return 0;
    }
    if (dp[left - 1] != 0) {
        return dp[left - 1];
    }
    int min = Integer.MAX_VALUE;
    for (int coin : coins) {
        int tmp = helper(coins, left - coin, dp);
        if (tmp >= 0) {
            if (tmp < min) {
                min = tmp + 1;
            }
        }
    }
    dp[left - 1] = (min == Integer.MAX_VALUE ? -1 : min);
    return dp[left - 1];
}

踩过的坑：[186,419,83,408],6249 这组。

  首先确定这题绝对不是贪心。然后其实如果你知道amount = 500怎么求的话，其实500以下的所有数字你也知道怎么求了。然后算法有个出口，我之前搓一直错在这里，就是如果dp[left - 1] != 0，这里我之前写的是大于，其实如果是-1也算找到了答案，所以要改成不等于0，其他的应该就没难度了。

时间复杂度O(n*amount) n为coins这个数组的长度

空间复杂度O(amount)

---