LeetCode link

first thought

  • sort the input array
  • check from biggest to smallest
  • pick current coin from most to none

solution

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
public class Solution {
    int min;
    public int coinChange(int[] coins, int amount) {
        Arrays.sort(coins);
        this.min = -1;
        if (coins.length > 0) {
            this.helper(coins, amount, coins.length - 1, 0);
        }
        return this.min;
    }
    private void helper(int[] coins, int amount, int index, int count) {
        if (index < 0) {
            return;
        }
        if (amount == coins[index]) {
            if (this.min == -1 || this.min > count + 1) {
                this.min = count + 1;
            }
            return;
        }
        for (int i = index; i >= 0; i--) {
            int maxNum = amount / coins[i];
            for (int j = maxNum; j > 0; j--) {
                this.helper(coins, amount - coins[i] * j, i - 1, count + maxNum);
            }
        }
    }
}

problem

miss the situation when amount is 0…

reason

modification

add this case

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
public class Solution {
    int min;
    public int coinChange(int[] coins, int amount) {
        Arrays.sort(coins);
        this.min = -1;
        if (amount == 0) {
            return 0;
        }
        if (coins.length > 0) {
            this.helper(coins, amount, coins.length - 1, 0);
        }
        return this.min;
    }
    private void helper(int[] coins, int amount, int index, int count) {
        if (index < 0) {
            return;
        }
        if (amount == coins[index]) {
            if (this.min == -1 || this.min > count + 1) {
                this.min = count + 1;
            }
            return;
        }
        for (int i = index; i >= 0; i--) {
            int maxNum = amount / coins[i];
            for (int j = maxNum; j > 0; j--) {
                this.helper(coins, amount - coins[i] * j, i - 1, count + maxNum);
            }
        }
    }
}

problem

wrong answer

reason

  • actually the first problem has already reveal the problem.The base case in the recursion is totally wrong.It should be the one which we make the amount is 0.And there’s also no need to add a individual case.
  • and there’s another stupid mistake: count + maxNum. It should be count + j

modification

change the base case into amount == 0

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
public class Solution {
    int min;
    public int coinChange(int[] coins, int amount) {
        Arrays.sort(coins);
        this.min = -1;
        if (coins.length > 0) {
            this.helper(coins, amount, coins.length - 1, 0);
        }
        return this.min;
    }
    private void helper(int[] coins, int amount, int index, int count) {
        if (amount == 0) {
            if (this.min == -1 || this.min > count) {
                this.min = count;
            }
            return;
        }
        if (index < 0) {
            return;
        }
        for (int i = index; i >= 0; i--) {
            int maxNum = amount / coins[i];
            for (int j = maxNum; j > 0; j--) {
                this.helper(coins, amount - coins[i] * j, i - 1, count + j);
            }
        }
    }
}

problem

TLE

modification

tried to skip some unnecessary loop, but it didn’t work.

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
public class Solution {
    int min;
    public int coinChange(int[] coins, int amount) {
        Arrays.sort(coins);
        this.min = -1;
        if (coins.length > 0) {
            this.helper(coins, amount, coins.length - 1, 0);
        }
        return this.min;
    }
    private void helper(int[] coins, int amount, int index, int count) {
        if (amount == 0) {
            if (this.min == -1 || this.min > count) {
                this.min = count;
            }
            return;
        }
        if (index < 0) {
            return;
        }
        for (int i = index; i >= 0; i--) {
            int maxNum = amount / coins[i];
            if (this.min != -1 && maxNum > this.min) {
                return;
            }
            for (int j = maxNum; j > 0; j--) {
                this.helper(coins, amount - coins[i] * j, i - 1, count + j);
            }
        }
    }
}

this can be solved using DP. Update later.

DP solution

first thought

  • similar with the 0-1 knapsack, build the 2d array to represent the count of two factors: current coin and sum.
  • each point at the matrix represent the minimum count at this coin.
  • iterate the current coin for k times, which k is the number of current coin. And save the minimum count for the current coin.
  • iterate to the end, which is have chosen all the coins and the sum is amount.

solution

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 {
    public int coinChange(int[] coins, int amount) {
        int n = coins.length;
        int[][] minCount = new int[n + 1][amount + 1];
        for (int i = 0; i <= amount; i++) {
            minCount[0][i] = Integer.MAX_VALUE;
        }
        for (int i = 0; i <= n; i++) {
            minCount[i][0] = 0;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= amount; j++) {
                int count = Integer.MAX_VALUE;
                for (int k = 0; k <= j / coins[i - 1]; k++) {
                    if (minCount[i - 1][j - k * coins[i - 1]] < Integer.MAX_VALUE) {
                        count = Math.min(minCount[i - 1][j - k * coins[i - 1]] + k, count);
                    }
                }
                minCount[i][j] = count;
            }
        }
        return minCount[n][amount] == Integer.MAX_VALUE ? -1 : minCount[n][amount];
    }
}

problem

TLE at the last case…

promote

The solution is right, but it can also make some pruning. There’re some situations that can be optimized.

  • In initializing the matrix, there’s no necessary using n+1 rows.
  • If the amount is smaller than the current coin. There’s no necessary to calculate.

modification

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 {
    public int coinChange(int[] coins, int amount) {
        int n = coins.length;
        int[][] minCount = new int[n][amount + 1];
        for (int i = 0; i <= amount; i++) {
            if (i % coins[0] == 0) {
                minCount[0][i] = i / coins[0];
            } else {
                minCount[0][i] = Integer.MAX_VALUE;
            }
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= amount; j++) {
                if (j < coins[i]) {
                    minCount[i][j] = minCount[i - 1][j];
                    continue;
                }
                int count = Integer.MAX_VALUE;
                for (int k = 0; k <= j / coins[i]; k++) {
                    if (minCount[i - 1][j - k * coins[i]] < Integer.MAX_VALUE) {
                        count = Math.min(minCount[i - 1][j - k * coins[i]] + k, count);
                    }
                }
                minCount[i][j] = count;
            }
        }
        return minCount[n - 1][amount] == Integer.MAX_VALUE ? -1 : minCount[n - 1][amount];
    }
}