Coin Change
Time: O(amount·coins)Space: O(amount)Find the minimum number of coins that sum to a target amount. A 1D DP where dp[a] = min coins to make amount a, built bottom-up from dp[0]=0.
SlowFast
1 / 47DP Table
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
coins
0
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
Inputs
Phase
Fill Table
Description
Initialize: dp[0]=0 (0 coins to make $0), dp[1..41]=∞. Coins: [1, 5, 10, 25]
Legend
Default
Active cell
Backtrack path
Header