动态规划算法leetcode.322

public static int coinChange(int[] coins, int amount) {
        int n=coins.length;
        Arrays.sort(coins);//排序
        int[] dp=new int[amount+1];//组成i最少数量
        Arrays.fill(dp,amount+1);//无法组成数量为amount+1
        dp[0]=0;//初始化
        for (int i = 1; i <=amount; i++) {
            //遍历每个coin并找出最少数量
            for (int j = 0; j < n; j++) {
                if(coins[j]>i)
                    break;
                else
                    dp[i]=Math.min(dp[i],dp[i-coins[j]]+1);
            }
        }
        if(dp[amount]>amount)
            return -1;
        else
            return dp[amount];
    }