Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Coin Change
Bookmark
Recursion
Memoization
Bottom-Up DP
Input
Example 1
Example 2 (impossible)
Example 3
Custom
amount
=
11
,
coins
=
[1, 2, 5]
coins
1
2
5
coins
1
2
5
coins
1
2
5
11
10
9
8
7
6
5
4
3
2
1
0
-1
-4
0
-3
1
0
-1
-4
-2
2
1
0
-1
-4
0
-3
-1
3
2
1
0
-1
-4
0
-3
1
0
-1
solve(3 - 1) = solve(2)
coins
1
2
5
11
10
9
8
7
6
5
4
3
2
1
1
1
0
0
-1
x
-4
x
0
0
-3
x
1
0
-1
-4
-2
2
1
0
-1
-4
0
-3
-1
3
2
1
0
-1
-4
0
-3
1
0
-1
try coin 2 on 3
coins
1
2
5
11
10
9
8
7
6
5
4
3
2
2
1
1
1
0
0
-1
x
-4
x
0
0
-3
x
1
1
0
0
-1
x
-4
x
-2
x
2
1
0
-1
-4
0
-3
-1
3
2
1
0
-1
-4
0
-3
1
0
-1
best for 1 is unknown so far
coins
1
2
5
11
10
9
8
7
6
5
4
2
3
2
2
1
1
1
0
0
-1
x
-4
x
0
0
-3
x
1
1
0
0
-1
x
-4
x
-2
x
2
1
1
1
0
0
-1
x
-4
x
0
0
-3
x
-1
x
3
2
1
0
-1
-4
0
-3
1
0
-1
2 + 1 = 3 coins via 1
coins
1
2
5
11
10
9
8
7
6
5
4
2
3
2
2
1
1
1
0
0
-1
x
-4
x
0
0
-3
x
1
1
0
0
-1
x
-4
x
-2
x
2
1
1
1
0
0
-1
x
-4
x
0
0
-3
x
-1
x
3
2
1
1
0
0
-1
x
-4
x
0
0
-3
1
0
-1
solve(2 - 5) = solve(-3)
coins
1
2
5
11
10
9
8
7
6
5
4
2
3
2
2
1
1
1
0
0
-1
x
-4
x
0
0
-3
x
1
1
0
0
-1
x
-4
x
-2
x
2
1
1
1
0
0
-1
x
-4
x
0
0
-3
x
-1
x
3
2
2
1
1
1
0
0
-1
x
-4
x
0
0
-3
x
1
1
0
0
-1
x
solve(0)
coins
1
2
5
11
10
9
8
7
6
5
1
4
2
3
2
2
1
1
1
0
0
-1
x
-4
x
0
0
-3
x
1
1
0
0
-1
x
-4
x
-2
x
2
1
1
1
0
0
-1
x
-4
x
0
0
-3
x
-1
x
3
2
2
1
1
1
0
0
-1
x
-4
x
0
0
-3
x
1
1
0
0
-1
x
coin 5 leads nowhere
coins
1
2
5
11
10
9
8
7
6
5
1
4
2
3
2
2
1
1
1
0
0
-1
x
-4
x
0
0
-3
x
1
1
0
0
-1
x
-4
x
-2
x
2
1
1
1
0
0
-1
x
-4
x
0
0
-3
x
-1
x
3
2
2
1
1
1
0
0
-1
x
-4
x
0
0
-3
x
1
1
0
0
-1
x
try coin 5 on 3
coins
1
2
5
11
10
9
8
7
6
5
1
4
2
3
2
2
1
1
1
0
0
-1
x
-4
x
0
0
-3
x
1
1
0
0
-1
x
-4
x
-2
x
2
1
1
1
0
0
-1
x
-4
x
0
0
-3
x
-1
x
3
2
2
1
1
1
0
0
-1
x
-4
x
0
0
-3
x
1
1
0
0
-1
x
11 needs 3 coin(s)
algo
master
.
io
Step:
Coins 1, 2, 5 and an amount of 11. Use as few coins as possible.
0 / 322
Input
Example 1
Example 2 (impossible)
Example 3
Custom
amount
=
11
,
coins
=
[1, 2, 5]
0 / 322
algo
master
.
io
Step:
Coins 1, 2, 5 and an amount of 11. Use as few coins as possible.
