By Long Luo
This article is the solution 3 Approaches: DFS, BFS, DP of Problem 322. Coin Change.
Here shows 3 Approaches to slove this problem: DFS, BFS and Dynamic Programming.
DFS
TLE!
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
| class Solution { int minCount = Integer.MAX_VALUE;
public int coinChange(int[] coins, int amount) { if (amount <= 0) { return 0; }
minCount = Integer.MAX_VALUE; dfs(coins, amount, 0); return minCount == Integer.MAX_VALUE ? -1 : minCount; }
private int dfs(int[] coins, int remain, int count) { if (remain < 0) { return -1; }
if (remain == 0) { minCount = Math.min(minCount, count); return count; } for (int x : coins) { dfs(coins, remain - x, count + 1); }
return -1; } }
|
Sorting the array first, then use DFS:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
| class Solution { int minAns = Integer.MAX_VALUE; public int coinChange(int[] coins, int amount) { Arrays.sort(coins); minAns = Integer.MAX_VALUE; coinChange(coins, amount, coins.length - 1, 0); return minAns == Integer.MAX_VALUE ? -1 : minAns; }
private void coinChange(int[] coins, int amount, int index, int cnt) { if (amount == 0) { minAns = Math.min(minAns, cnt); return; }
if (index < 0) { return; }
for (int k = amount / coins[index]; k >= 0 && k + cnt < minAns; k--) { coinChange(coins, amount - k * coins[index], index - 1, cnt + k); } } }
|
Memory DFS:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
| public class Solution { public int coinChange(int[] coins, int amount) { if (amount <= 0) { return 0; }
return coinChange(coins, amount, new int[amount]); }
private int coinChange(int[] coins, int rem, int[] count) { if (rem < 0) { return -1; }
if (rem == 0) { return 0; }
if (count[rem - 1] != 0) { return count[rem - 1]; }
int min = Integer.MAX_VALUE; for (int coin : coins) { int res = coinChange(coins, rem - coin, count); if (res >= 0 && res < min) { min = 1 + res; } } count[rem - 1] = (min == Integer.MAX_VALUE) ? -1 : min; return count[rem - 1]; } }
|
Analysis
- Time Complexity: O(amount×n)
- Space Complexity: O(amount)
BFS
TLE!
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
| public int coinChange(int[] coins, int amount) { if (amount <= 0) { return 0; }
int minAns = Integer.MAX_VALUE; int len = coins.length; Arrays.sort(coins);
for (int i = len - 1; i >= 0; i--) { if (amount % coins[i] == 0) { minAns = Math.min(minAns, amount / coins[i]); break; }
int divide = amount / coins[i]; for (int j = divide; j >= 0; j--) { Queue<int[]> queue = new LinkedList<>(); queue.offer(new int[]{amount - j * coins[i], j}); while (!queue.isEmpty()) { int[] cur = queue.poll(); if (cur[0] == 0) { minAns = Math.min(minAns, cur[1]); }
for (int x : coins) { if (x > cur[0]) { break; }
queue.offer(new int[]{cur[0] - x, cur[1] + 1}); } } } }
return minAns == Integer.MAX_VALUE ? -1 : minAns; }
|
BFS Opt:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
| class Solution { public int coinChange(int[] coins, int amount) { if (amount <= 0) { return 0; }
Arrays.sort(coins);
Queue<Integer> queue = new LinkedList<>(); queue.offer(amount);
boolean[] visited = new boolean[amount + 1]; visited[amount] = true;
int step = 1; while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { Integer cur = queue.poll(); for (int x : coins) { int target = cur - x; if (target == 0) { return step; } if (target < 0) { break; } if (!visited[target]) { visited[target] = true; queue.offer(target); } } }
step++; }
return -1; } }
|
Analysis
- Time Complexity: O(amount×n)
- Space Complexity: O(amount)
DP
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
| public int coinChange(int[] coins, int amount) { if (amount <= 0) { return 0; }
int[] dp = new int[amount + 1]; dp[0] = 0;
for (int x : coins) { if (x > amount) { continue; } dp[x] = 1; }
for (int i = 1; i <= amount; i++) { if (dp[i] > 0) { continue; }
for (int x : coins) { if (i >= x && dp[i - x] > 0) { dp[i] = dp[i] > 0 ? Math.min(dp[i], dp[i - x] + 1) : dp[i - x] + 1; } } }
return dp[amount] == 0 ? -1 : dp[amount]; }
|
DP Opt:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| public int coinChange(int[] coins, int amount) { int max = amount + 1;
int[] dp = new int[max]; Arrays.fill(dp, max);
dp[0] = 0; for (int i = 1; i <= amount; i++) { for (int x : coins) { if (i >= x) { dp[i] = Math.min(dp[i], dp[i - x] + 1); } } }
return dp[amount] > amount ? -1 : dp[amount]; }
|
Analysis
- Time Complexity: O(amount×n)
- Space Complexity: O(amount)
All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions. 😉😃💗