Coin Change

The key idea

Build the answer bottom-up: dp[a] is the fewest coins to make amount a. To make a you spend one coin c and then need dp[a - c] more, so dp[a] = min over coins c of dp[a - c] + 1. Reuse the smaller answers instead of re-searching.

Problem

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.

Constraints

1 <= coins.length <= 12
1 <= coins[i] <= 2^31 - 1
0 <= amount <= 10^4

Examples

Input: coins = [1,2,5], amount = 11 Output: 3

Input: coins = [2], amount = 3 Output: -1

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

Complexity

Time: O(amount * n) Space: O(amount)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →