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

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 4.5k 阅读时长 ≈ 4 分钟

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