Knapsack or Coin Change DP | Dataford Interview Questions

Design and implement a function to solve a classic dynamic programming problem such as the knapsack problem or coin change problem, and explain your complexity trade-offs. Implement the coin change variant below using coin_change(coins, amount); return the minimum number of coins needed to form amount, or -1 if it is impossible. Coins may be reused, and return 0 when amount is zero. For example, [1, 2, 5], 11 returns 3, while [2], 3 returns -1.

Constraints

1 <= len(coins) <= 100
1 <= coins[i] <= 10^4
0 <= amount <= 10^4
Coins may be reused any number of times
Return -1 when the amount is unreachable

Function Signature

def coin_change(coins, amount):

Your question is Knapsack or Coin Change DP. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

Constraints

1 <= len(coins) <= 100
1 <= coins[i] <= 10^4
0 <= amount <= 10^4
Coins may be reused any number of times
Return -1 when the amount is unreachable

Function Signature

def coin_change(coins, amount):

Your question is Knapsack or Coin Change DP. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.