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 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.

分析

典型的DP问题。注意这里的硬币是可以无限使用的，另外注意下无法兑换返回-1的处理。

这道题要求是返回硬币个数，显然Follow up可以是在最少硬币的情况下，返回具体的硬币值

我能想到的比较直接的方法就是用一个map对于每个可以组合的amount用一个List存对应的硬币组合，然后同样是DP的方法找到最小硬币组合，更新组合。

复杂度

time: O(n*m), space: O(n), n表示amount，m表示硬币个数。

代码

public class Solution {    public int coinChange(int[] coins, int amount) {        // 无效输入的处理        if (amount == 0)            return 0;        if (coins == null || coins.length == 0)            return -1;                    int[] dp = new int[amount + 1];        for (int i = 1; i <= amount; i++) {            int min = Integer.MAX_VALUE;            for (int j = 0; j < coins.length; j++) {                if (i >= coins[j] && dp[i - coins[j]] != -1)                    min = Math.min(min, dp[i - coins[j]] + 1);            }                        // 根据min的值判断是否能兑换            dp[i] = min == Integer.MAX_VALUE ? -1 : min;        }        return dp[amount];    }}