Coin Change

Medium

dynamic-programming

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.

Recurrence Relation: dp[amount] = min(dp[amount - coin] + 1) for all coins

This is a classic unbounded knapsack problem. For each amount, we try each coin and take the minimum.

Example 1

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

Output: 3

Explanation: 11 = 5 + 5 + 1, so we need 3 coins.

Example 2

Input: coins = [2], amount = 3

Output: -1

Explanation: You cannot make 3 with only coins of value 2.

Example 3

Input: coins = [1], amount = 0

Output: 0

Explanation: No coins needed to make amount 0.

Constraints

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

Show Hints (4)

Hint 1: Build up solutions from smaller amounts to larger amounts.

Hint 2: For each amount, try using each coin denomination.

Hint 3: dp[i] represents the minimum coins needed to make amount i.

Hint 4: If we use a coin of value c, we need 1 + dp[i-c] coins (if dp[i-c] exists).

Loading editor...

Test Results

Click "Run" to execute your code against test cases

AI Tutor

Socratic guidance - I'll ask questions, not give answers

AI Tutor

Hello! I'm your AI tutor, here to guide you through this problem using the Socratic method. I won't give you direct answers, but I'll ask questions and provide hints to help you discover the solution yourself. What's your first instinct when you look at this problem? What approach comes to mind?