Question Link:

https://leetcode.com/problems/coin-change/

Question Description

Given coins array, and amount, compute the minimum number of coins to sum up at the amount.
Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Simulation

Wrong Solution: Greedy

Greedy based on the maximum coin first.

Example

Unsatisified case: [2,3,5] amount= 19 -> 19-5-5-5-3 = 1
However it can be computed as 19-5-5-5-2-2 = 0

Solution 1: Breadth First Search

Example

Input: Coins = [1,2,5], Amount= 11

LeetCode 322 Coin Change - 图1

Solution 2: Dynamic Programming

Example

Input: Coins = [1,2,5], Amount= 11
LeetCode 322 Coin Change - 图2

Implementation

Solution 1: Time Limit Exceeded

  1. public int coinChange(int[] coins, int amount) {
  2.     if (amount == 0) return 0;
  3.     Queue < Integer > queue = new LinkedList < > ();
  4.     queue.add(amount);
  5.     int count = 0;
  6.     while (!queue.isEmpty()) {
  7.         int size = queue.size();
  8.         for (int i = 0; i < size; i++) {
  9.             int cur = queue.poll();
  10.             if (cur == 0) {
  11.                 return count;
  12.             }
  13.             for (int coin: coins) {
  14.                 if (cur - coin >= 0) {
  15.                     queue.add(cur - coin);
  16.                 }
  17.             }
  18.         }
  19.         count++;
  20.     }
  21.     return -1;
  22. }

Solution 1.1 Optimization of Solution 1

  1. public int coinChange(int[] coins, int amount) {
  2.     if (amount == 0) return 0;
  3.     Set < Integer > cache = new HashSet < > ();
  4.     Queue < Integer > queue = new LinkedList < > ();
  5.     queue.add(amount);
  6.     cache.add(amount);
  7.     int count = 0;
  8.     while (!queue.isEmpty()) {
  9.         int size = queue.size();
  10.         for (int i = 0; i < size; i++) {
  11.             int cur = queue.poll();
  12.             if (cur == 0) {
  13.                 return count;
  14.             }
  15.             for (int coin: coins) {
  16.                 if (cur - coin >= 0) {
  17.                     if (!cache.contains(cur - coin)) {
  18.                         queue.add(cur - coin);
  19.                         cache.add(cur - coin);
  20.                     }
  21.                 }
  22.             }
  23.         }
  24.         count++;
  25.     }
  26.     return -1;
  27. }

Solution 2: Dynamic Programming (Iterative Approach)

Time Complexity: O(numberofCoins*TotalAmount)

public int coinChange_dp(int[] coins, int amount) {
    if (amount < 1) return 0;
    int[] dp = new int[amount + 1];
    int sum = 0;
    while (++sum <= amount) {
        int min = -1;
        for (int coin: coins) {
            if (sum >= coin && dp[sum - coin] != -1) {
                int temp = dp[sum - coin] + 1;
                min = min < 0 ? temp : Math.min(temp, min);
            }
        }
        dp[sum] = min;
    }
    return dp[amount];
}

Solution 2.1: Dynamic Programming (Recursive Approach)

public int coinChange(int[] coins, int amount) {
    if (amount < 1) return 0;
    return helper(coins, amount, new int[amount]);
}

private int helper(int[] coins, int rem, int[] count) { // rem: remaining coins after the last step; count[rem]: minimum number of coins to sum up to rem
    if (rem < 0) return -1; // not valid
    if (rem == 0) return 0; // completed
    if (count[rem - 1] != 0) return count[rem - 1]; // already computed, so reuse
    int min = Integer.MAX_VALUE;
    for (int coin: coins) {
        int res = helper(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];
}