Learn
Practice
Newsletter
Resources
Mobile
New
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Perfect Squares
Bookmark
Input
Example 1 (3)
Example 2 (2)
Small (4)
Perfect square (1)
Medium (2)
Custom
n
=
12
squares
1²
1
2²
4
3²
9
n =
12
fewest perfect squares that sum to 12? squares can repeat
squares
1²
1
2²
4
3²
9
n =
12
fewest perfect squares that sum to 12? squares can repeat
squares
1²
1
2²
4
3²
9
n =
12
sq
+1
dp
0
0
1
1
2
2
∞
3
∞
4
∞
5
∞
6
∞
7
∞
8
∞
9
∞
10
∞
11
∞
12
i-1 = 1
i = 2
dp[2]
=
2
new best,
2
<
∞
squares
1²
1
2²
4
3²
9
n =
12
sq
+4
dp
0
0
1
1
2
2
3
3
4
4
∞
5
∞
6
∞
7
∞
8
∞
9
∞
10
∞
11
∞
12
i-4 = 0
i = 4
end with
2² = 4
: dp[
0
] + 1 =
0
+ 1 =
1
vs dp[4] =
4
squares
1²
1
2²
4
3²
9
n =
12
dp
0
0
1
1
2
2
3
3
1
4
2
5
∞
6
∞
7
∞
8
∞
9
∞
10
∞
11
∞
12
i = 5
amount 5 settled:
dp[5]
=
2
squares
1²
1
2²
4
3²
9
n =
12
sq
+1
dp
0
0
1
1
2
2
3
3
1
4
2
5
3
6
4
7
∞
8
∞
9
∞
10
∞
11
∞
12
i-1 = 6
i = 7
dp[7]
=
4
new best,
4
<
∞
squares
1²
1
2²
4
3²
9
n =
12
sq
+4
dp
0
0
1
1
2
2
3
3
1
4
2
5
3
6
4
7
2
8
∞
9
∞
10
∞
11
∞
12
i-4 = 4
i = 8
dp[8]
=
2
new best,
2
<
5
squares
1²
1
2²
4
3²
9
n =
12
dp
0
0
1
1
2
2
3
3
1
4
2
5
3
6
4
7
2
8
1
9
∞
10
∞
11
∞
12
i = 9
amount 9 settled:
dp[9]
=
1
squares
1²
1
2²
4
3²
9
n =
12
dp
0
0
1
1
2
2
3
3
1
4
2
5
3
6
4
7
2
8
1
9
2
10
∞
11
∞
12
i = 10
amount 10 settled:
dp[10]
=
2
squares
1²
1
2²
4
3²
9
n =
12
dp
0
0
1
1
2
2
3
3
1
4
2
5
3
6
4
7
2
8
1
9
2
10
3
11
∞
12
i = 12
i = 12
which square ends the best sum for
12
?
squares
1²
1
2²
4
3²
9
n =
12
-4
-4
-4
dp
0
0
1
1
2
2
3
3
1
4
2
5
3
6
4
7
2
8
1
9
2
10
3
11
3
12
12 =
4 + 4 + 4
, 3 squares
algo
master
.
io
Step:
Fewest perfect squares that sum to 12?
0 / 76
Input
Example 1 (3)
Example 2 (2)
Small (4)
Perfect square (1)
Medium (2)
Custom
n
=
12
0 / 76
algo
master
.
io
Step:
Fewest perfect squares that sum to 12?
