动态规划算法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]; }