Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Coin Change
Bookmark
Input
Example 1
Example 2 (impossible)
Example 3
Custom
amount
=
11
,
coins
=
[1, 2, 5]
coins
1
2
5
amount =
11
fewest coins that add up to 11? coins can repeat
coins
1
2
5
amount =
11
fewest coins that add up to 11? coins can repeat
coins
1
2
5
amount =
11
coin
+1
dp
0
0
1
1
∞
2
∞
3
∞
4
∞
5
∞
6
∞
7
∞
8
∞
9
∞
10
∞
11
i-1 = 1
i = 2
end with
1
: dp[
1
] + 1 =
1
+ 1 =
2
vs dp[2] =
∞
coins
1
2
5
amount =
11
coin
+2
dp
0
0
1
1
1
2
2
3
∞
4
∞
5
∞
6
∞
7
∞
8
∞
9
∞
10
∞
11
i-2 = 1
i = 3
end with
2
: dp[
1
] + 1 =
1
+ 1 =
2
vs dp[3] =
2
coins
1
2
5
amount =
11
dp
0
0
1
1
1
2
2
3
2
4
∞
5
∞
6
∞
7
∞
8
∞
9
∞
10
∞
11
i = 4
amount 4 settled:
dp[4]
=
2
coins
1
2
5
amount =
11
dp
0
0
1
1
1
2
2
3
2
4
1
5
∞
6
∞
7
∞
8
∞
9
∞
10
∞
11
i = 6
i = 6
which coin ends the best way to pay
6
?
coins
1
2
5
amount =
11
coin
+1
dp
0
0
1
1
1
2
2
3
2
4
1
5
2
6
3
7
∞
8
∞
9
∞
10
∞
11
i-1 = 6
i = 7
dp[7]
=
3
new best,
3
<
∞
coins
1
2
5
amount =
11
coin
+2
dp
0
0
1
1
1
2
2
3
2
4
1
5
2
6
2
7
3
8
∞
9
∞
10
∞
11
i-2 = 6
i = 8
end with
2
: dp[
6
] + 1 =
2
+ 1 =
3
vs dp[8] =
3
coins
1
2
5
amount =
11
coin
+5
dp
0
0
1
1
1
2
2
3
2
4
1
5
2
6
2
7
3
8
3
9
∞
10
∞
11
i-5 = 4
i = 9
end with
5
: dp[
4
] + 1 =
2
+ 1 =
3
vs dp[9] =
3
coins
1
2
5
amount =
11
coin
+5
dp
0
0
1
1
1
2
2
3
2
4
1
5
2
6
2
7
3
8
3
9
2
10
∞
11
i-5 = 5
i = 10
dp[10]
=
2
new best,
2
<
4
coins
1
2
5
amount =
11
-1
-5
-5
dp
0
0
1
1
1
2
2
3
2
4
1
5
2
6
2
7
3
8
3
9
2
10
3
11
11 =
1 + 5 + 5
, 3 coins
algo
master
.
io
Step:
Fewest coins that add up to 11?
0 / 86
Input
Example 1
Example 2 (impossible)
Example 3
Custom
amount
=
11
,
coins
=
[1, 2, 5]
0 / 86
algo
master
.
io
Step:
Fewest coins that add up to 11?
