class Solution { public int coinChange(int[] coins, int amount) { int max = Integer.MAX_VALUE; int[] dp = new int[amount + 1]; // 题目要取得最小,那么初始化要为max,和T279一样 for(int i = 0; i <= amount; i++) dp[i] = max; dp[0] = 0; // 遍历背包 for(int i = 1; i <= amount; i++){ // 遍历物品 for(int j = 0; j < coins.length; j++){ if(i >= coins[j] && dp[i - coins[j]] != max){ dp[i] = Math.min(dp[i - coins[j]] + 1, dp[i]); } } } return dp[amount] == max ? -1 : dp[amount]; } }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)