Coin Change

optimizationminimum-coinsunbounded

Press play to start

1function coinChange(coins: number[], amount: number): number {
const dp = Array(amount + 1).fill(Infinity)
dp[0] = 0
for (let a = 1; a <= amount; a++) {
  for (const c of coins) {
    if (c <= a && dp[a - c] + 1 < dp[a])
      dp[a] = dp[a - c] + 1
  }
}
return dp[amount] === Infinity ? -1 : dp[amount]
11}

Step 1/0

Custom array:

Complexity

Best:O(amount·n)
Average:O(amount·n)
Worst:O(amount·n)
Space:O(amount)

Description

Finds the minimum number of coins needed to make a given amount, given an array of coin denominations.

When to use

Currency systems, vending machines, any problem requiring minimum resources to reach a target.