Question

Formatted question description: https://leetcode.ca/all/322.html

 322	Coin Change

 You are given coins of different denominations and a total amount of money amount.
 Write a function to compute the fewest number of coins that you need to make up that amount.

 If that amount of money cannot be made up by any combination of the coins, return -1.

 Example 1:

 Input: coins = [1, 2, 5], amount = 11
 Output: 3
 Explanation: 11 = 5 + 5 + 1

 Example 2:

 Input: coins = [2], amount = 3
 Output: -1

 Note:
 You may assume that you have an infinite number of each kind of coin.

 @tag-dp

Algorithm

We maintain a one-dimensional dynamic array dp, where dp[i] represents the change of the smallest number of coins when the amount of money is i. Note that since the array starts from 0, one more bit must be applied. The size of the array is amount +1, so the final result can be saved in dp[amount].

Initialize dp[0] = 0, because if the target value is 0, no coins are needed. Other values ​​can be initialized as amount+1, why? Because the smallest coin is 1, so amount requires at most amount coins, and amount+1 is equivalent to the current maximum.

  • Note that the integer maximum value cannot be used for initialization here, because there is an operation of adding 1 to the subsequent state transition equation, which may cause overflow.

The next step is to find the state transition equation. Example 1, suppose I take a coin with a value of 5, then since the target value is 11, so if we know dp[6], then we know the dp of 11 Worth it?

So the way to update dp[i] is to traverse each coin. If the value of the traversed coin is less than the value of i (for example, a coin with a value of 5 cannot be used to update dp[3]), use dp[i-coins[j ]] + 1 to update dp[i], so the state transition equation is:

dp[i] = min(dp[i], dp[i-coins[j]] + 1);

among them

  • coins[j] is the j-th coin
  • i-coins[j] is the amount of money i minus the value of one of the coins, the remaining amount of money is found in the dp array

Then add 1 and compare the value in the current dp array, and update the dp array with the smaller one.

Code

Java

import java.util.Arrays;

public class Coin_Change {

    public static void main(String[] args) {
        Coin_Change out = new Coin_Change();
        Solution s = out.new Solution();

        System.out.println(s.coinChange(new int[]{186,419,83,408}, 6249)); // 20
        System.out.println(s.coinChange(new int[]{1, 2, 5}, 11)); // 3
    }


    class Solution {
        public int coinChange(int[] coins, int amount) {

            // dp[i] means, min count to achieveamount i
            int[] dp = new int[amount + 1];

            // @note:@memorize: final result could not be bigger than it
            // still, leetcode article still possible to be overflowed, convert int to long is a better solution
            //  eg. amount is Integer.MAX_VALUE, then here +1 will screw it up
            int upperBoundCheck = amount + 1;
            for (int i = 1; i < dp.length; i++) {
//                dp[i] = Integer.MAX_VALUE;
                dp[i] = upperBoundCheck; // not reachable value
            }
//            @note: util function
//            Arrays.fill(dp, upperBoundCheck);

            dp[0] = 0;

            for (int target = 1; target <= amount; target++) {

                for (int i = 0; i < coins.length; i++) {

                    if (target - coins[i] >= 0) {
                        dp[target] = Math.min(dp[target], 1 + dp[target - coins[i]]);
                    }
                }
            }

            // dp[amount] == upperBoundCheck meaning it's never been udpated/reached
            return dp[amount] == upperBoundCheck ? -1 : dp[amount];
        }
    }


    /*
        @note:
        overflowed:
            [1,2147483647]
            2
    */
    class Solution_recursion {

        boolean isChangable = false;
        int count = Integer.MAX_VALUE;

        public int coinChange(int[] coins, int amount) {

            if (coins == null || coins.length == 0) {
                return -1;
            }

            Arrays.sort(coins);

            findChange(coins, amount, 0, 0);

            return isChangable? count : -1;
        }

        private void findChange(int[] coins, int amount, long sum, int count) {

            // @note: cannot terminate, could miss correct result
//            if (isChangable) {
//                return;
//            }

            if (sum > amount) {
                return;
            }

            if (sum == amount) {
                isChangable = true;
                this.count = Math.min(count, this.count);

                return;
            }

            for (int i = coins.length - 1; i >= 0; i--) {
                findChange(coins, amount, sum + coins[i], count + 1);
            }
        }
    }
}

All Problems

All Solutions