题目描述

算法思想

举例说明算法的思想，假设现在有数组[1,2,3]，请从数组中找到最少的硬币个数凑成纸币6。

共两层遍历，第一层遍历是从使用数组中[0,0]的数组的值，第二层，来找到所有[0,6]这些纸币需要的[0,0]中的硬币的个数的最小数。

第二次就是第一层使用数组中[0,1]的数组的值，第二层，来找到所有[0,6]这些纸币需要的[0,1]中的硬币的个数的最小数。

第三次就是第一层循环使用数组中[0,2]的数组的值，第二层，来找到所有[0,6]中这些纸币需要的[0,2]中的一笔的个数的最小数。

简言之，就是利用之前的结果，并且再加上一个数字后，看看使用这个数字后，是否能够使使用的硬币的个数达到最小。

代码实现

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        Arrays.fill(dp, 1, amount+1, Integer.MAX_VALUE);

        for(int i = 0; i < coins.length; i++){
            for(int j = coins[i]; j <= amount; j++){
                if(dp[j - coins[i]] != Integer.MAX_VALUE){
                    dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
                }
            }
        }
        if(dp[amount] != Integer.MAX_VALUE){
            return dp[amount];
        }
        return -1;
    }
}