• 微信公众号：美女很有趣。 工作之余，放松一下，关注即送10G+美女照片！

# LeetCode：322. 零钱兑换

4小时前 2次浏览

``````输入：coins = [1, 2, 5], amount = 11

1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104
``````

BFS + 剪枝

``````class Solution {
public int coinChange(int[] coins, int amount) {
queue.offer(amount);
int length = coins.length, res = 0;
boolean[] visited = new boolean[amount + 1];

while (!queue.isEmpty()) {
int len = queue.size();
for (int j = 0; j < len; j++) {
int num = queue.poll();
if (num == 0) {
return res;
}

for (int i = 0; i < length; i++) {
if (num >= coins[i] && !visited[num - coins[i]]) {
visited[num - coins[i]] = true;
queue.offer(num - coins[i]);
}
}
}
res++;
}

return -1;
}
}
``````

DP：

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

for (int i = 1; i <= amount; i++) {
for (int num : coins) {
if (i >= num) {
dp[i] = Math.min(dp[i - num] + 1, dp[i]);
}
}
}

return dp[amount] == (amount + 1) ? -1 : dp[amount];
}
}
``````