Coin Change
Fewest coins for amount a = 1 + min over coins c of best(a - c). Ways variant counts combinations.
DP in One Row: Fewest coins for 6 from 1, 3, 4
Amount 1. 1: 1 + dp[0] = 1. Keep the smallest: dp[1] = 1, ending with a 1 coin.
Cost
- Best
- O(a * c)
- Average
- O(a * c)
- Worst
- O(a * c)
- Space
- O(a)
Before this
Variants
- Minimum Coins
- Count Ways
Related
Taught by the same lesson
DP in One Row covers these too, in the same run.