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 ( a m o u n t × n ) O(amount \times n) O ( a m o u n t × n )
Space Complexity : O ( a m o u n t ) O(amount) O ( a m o u n t )
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 ( a m o u n t × n ) O(amount \times n) O ( a m o u n t × n )
Space Complexity : O ( a m o u n t ) O(amount) O ( a m o u n t )
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 ( a m o u n t × n ) O(amount \times n) O ( a m o u n t × n )
Space Complexity : O ( a m o u n t ) O(amount) O ( a m o u n t )
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 . 😉😃💗