Question

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

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return 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.

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

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

Example 3:

Input: coins = [1], amount = 0
Output: 0

Constraints:

1 <= coins.length <= 12
1 <= coins[i] <= 2³¹ - 1
0 <= amount <= 10⁴

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

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);
            }
        }
    }
}

############

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for (int coin : coins) {
            for (int j = coin; j <= amount; j++) {
                dp[j] = Math.min(dp[j], dp[j - coin] + 1);
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

// OJ: https://leetcode.com/problems/coin-change/
// Time: O(NT)
// Space: O(NT)
class Solution {
public:
    int coinChange(vector<int>& A, int T) {
        sort(begin(A), end(A), greater<>());
        int N = A.size(), INF = 0x3f3f3f3f, dp[13][10001] = {};
        memset(dp, 0x3f, sizeof(dp));
        for (int i = 0; i <= N; ++i) dp[i][0] = 0;
        for (int i = 0; i < N; ++i) {
            for (int t = 1; t <= T; ++t) {
                dp[i + 1][t] = min(dp[i][t], t - A[i] >= 0 ? 1 + dp[i + 1][t - A[i]] : INF);
            }
        }
        return dp[N][T] == INF ? -1 : dp[N][T];
    }
};

'''
>>> float("inf")
inf
>>> float("inf") + 1
inf
'''

class Solution(object):
  def coinChange(self, coins, amount):
    """
    :type coins: List[int]
    :type amount: int
    :rtype: int
    """

    dp = [float("inf")] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
      for coin in coins:
        if i - coin >= 0:
          dp[i] = min(dp[i], dp[i - coin] + 1)
    return dp[-1] if dp[-1] != float("inf") else -1

############

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [amount + 1] * (amount + 1)
        dp[0] = 0
        for coin in coins:
            for j in range(coin, amount + 1):
                dp[j] = min(dp[j], dp[j - coin] + 1)
        return -1 if dp[-1] > amount else dp[-1]

func coinChange(coins []int, amount int) int {
	dp := make([]int, amount+1)
	for i := 1; i <= amount; i++ {
		dp[i] = amount + 1
	}
	for _, coin := range coins {
		for j := coin; j <= amount; j++ {
			dp[j] = min(dp[j], dp[j-coin]+1)
		}
	}
	if dp[amount] > amount {
		return -1
	}
	return dp[amount]
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

function coinChange(coins: number[], amount: number): number {
    let dp = new Array(amount + 1).fill(amount + 1);
    dp[0] = 0;
    for (const coin of coins) {
        for (let j = coin; j <= amount; ++j) {
            dp[j] = Math.min(dp[j], dp[j - coin] + 1);
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function (coins, amount) {
    let dp = Array(amount + 1).fill(amount + 1);
    dp[0] = 0;
    for (const coin of coins) {
        for (let j = coin; j <= amount; ++j) {
            dp[j] = Math.min(dp[j], dp[j - coin] + 1);
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
};

impl Solution {
    pub fn coin_change(coins: Vec<i32>, amount: i32) -> i32 {
        let n = coins.len();
        let amount = amount as usize;
        let mut dp = vec![amount + 1; amount + 1];
        dp[0] = 0;
        for i in 1..=amount {
            for j in 0..n {
                let coin = coins[j] as usize;
                if coin <= i {
                    dp[i] = dp[i].min(dp[i - coin] + 1);
                }
            }
        }
        if dp[amount] > amount {
            -1
        } else {
            dp[amount] as i32
        }
    }
}

322 - Coin Change

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions