Coin Change
Problem Description
Given an integer array coins of denominations and an integer amount, return the fewest coins needed to make up amount. If impossible, return -1. You have infinite coins of each denomination.
Example 1:
Input: coins = [1,2,5], amount = 11
Output: 3 (5+5+1)
Example 2:
Input: coins = [2], amount = 3
Output: -1
Example 3:
Input: coins = [1], amount = 0
Output: 0
DE Shaw Tier 1 — LC 322. Also practice LC 518 (count ways).
Optimal: Bottom-up DP O(amount * coins). dp[i] = min coins for amount i.
Recurrence: dp[i] = min(dp[i], dp[i - coin] + 1) for each coin <= i.
Example Test Cases
Example 1
Input: [[1,2,5],11]
Expected: 3
Example 2
Input: [[2],3]
Expected: -1
Example 3
Input: [[1],0]
Expected: 0
Example 4
Input: [[1,5,10,25],36]
Expected: 3
Run your code to see the results