[LeetCode][322. Coin Change] 3 Approaches: DFS, BFS, DP

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. 😉😃💗