Welcome to Subscribe On Youtube

322. Coin Change

Description

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] <= 231 - 1
  • 0 <= amount <= 104

Solutions

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.

  • class Solution {
    public int coinChange(int[] coins, int amount) {
        final int inf = 1 << 30;
        int n = amount;
        int[] f = new int[n + 1];
        Arrays.fill(f, inf);
        f[0] = 0;
        for (int x : coins) {
            for (int j = x; j <= n; ++j) {
                f[j] = Math.min(f[j], f[j - x] + 1);
            }
        }
        return f[n] >= inf ? -1 : f[n];
    }
}

  • class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n = amount;
        int f[n + 1];
        memset(f, 0x3f, sizeof(f));
        f[0] = 0;
        for (int x : coins) {
            for (int j = x; j <= n; ++j) {
                f[j] = min(f[j], f[j - x] + 1);
            }
        }
        return f[n] > n ? -1 : f[n];
    }
};

  • '''
>>> 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 {
	n := amount
	f := make([]int, n+1)
	for i := range f {
		f[i] = 1 << 30
	}
	f[0] = 0
	for _, x := range coins {
		for j := x; j <= n; j++ {
			f[j] = min(f[j], f[j-x]+1)
		}
	}
	if f[n] > n {
		return -1
	}
	return f[n]
}

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


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


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

All Problems

All Solutions