← All problems

Coin Change

medium

You're given an array coins of coin denominations and an integer amount. Return the fewest number of coins needed to make up amount (unlimited supply of each coin), or -1 if it can't be made.

Same table-filling idea as 0/1 Knapsack, except each coin can be reused — so the inner loop reads from the current row, not a previous one.

Example

Input: coins = [1, 2, 5], amount = 11
Output: 3        // 5 + 5 + 1
Loading...