leetcode322 零钱兑换

leetcode322 零钱兑换

思路：分析可知这是一道完全背包问题，主要代码为

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

但是要注意边界情况的处理，首先dp[0]赋值为0，所有元素赋值为最大值+1，这样在遍历的时候dp[i]（i为coins中元素)=dp[0]+1=1

再讨论一下需要返回-1的情况，比如coins为：[2,4] amount为5

这样在5的循环中，首先dp[5]=amount+1=6（初始状态），然后dp[5]=min(dp[5],d[5-2]+1)即dp[5]=min(6,d[3]+1)，dp[3]=min(6,dp[1]+1)=6所以dp[5]=6，可见只要最后dp[amount]>amount就返回-1

public class Solution {public int coinChange(int[] coins, int amount) {int max = amount + 1;int[] dp = new int[amount + 1];Arrays.fill(dp, max);dp[0] = 0;for (int i = 1; i <= amount; i++) {for (int j = 0; j < coins.length; j++) {if (coins[j] <= i) {dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);}}}if(dp[amount]>amount) return -1;return dp[amount];}
}