Basic Problemsminimizationlinear

Minimum Perfect Squares

Given a positive integer n, find the minimum number of perfect squares, such as 1, 4, 9, or 16, that add up to exactly n.

Do this lesson first: coin change

Example input

n = 12

Expected output

3

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

dp[i] = 1 + min over every j with j*j <= i of dp[i - j*j]

Ask what the last square added could have been. It is some j*j no larger than i, leaving a remainder of i - j*j behind, and whichever remainder already takes the fewest squares should be the one to extend, since the final square always adds exactly one more to the count. That is a min over candidates, not a sum, because only one final square actually got added.

dp[0] = 0 is the only base: making zero takes no squares at all, and it is a real answer, not a placeholder. Every cell from i = 1 up depends only on smaller indices (i - j*j for every j with j*j <= i), so filling left to right guarantees every candidate already holds a real value before it is read. At i = 1 there is only one candidate, j = 1, so this cell is filled by a genuine minimum with nothing else to compare it against.

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

dp[0] = 0 is the only base: making zero takes no squares at all, and it is a real answer, not a placeholder. Every cell from i = 1 up depends only on smaller indices (i - j*j for every j with j*j <= i), so filling left to right guarantees every candidate already holds a real value before it is read. At i = 1 there is only one candidate, j = 1, so this cell is filled by a genuine minimum with nothing else to compare it against.

i=0

i=1

i=2

i=3

i=4

i=5

i=6

i=7

i=8

i=9

i=10

i=11

i=12

0

1

2

3

1

2

3

4

2

1

2

3

minimum-perfect-squares.ts

1function numSquares(n) {
2 const dp = new Array(n + 1).fill(Infinity);
3 dp[0] = 0;
4 for (let i = 1; i <= n; i++) {
5 for (let j = 1; j * j <= i; j++) {
6 dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
7 }
8 }
9 return dp[n];
10}

Base caseComputedBeing readAnswer

The code, the trap, the variations

minimum-perfect-squares.ts

1function numSquares(n) {
2 const dp = new Array(n + 1).fill(Infinity);
3 dp[0] = 0;
4 for (let i = 1; i <= n; i++) {
5 for (let j = 1; j * j <= i; j++) {
6 dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
7 }
8 }
9 return dp[n];
10}

Where people go wrong

Assuming a greedy, largest-square-first strategy works. It does not: 12 is 4 + 4 + 4, three squares, not 9 + 1 + 1 + 1, four squares, even though 9 is the largest square not exceeding 12. Every candidate remainder has to be compared through the full table; there is no shortcut that skips checking the smaller squares too.

Use perfect cubes instead of perfect squares.
Only which values count as an allowed piece changes, from j*j to j*j*j; the same min-over-candidates recurrence and the same left-to-right order still apply.
Ask for the actual list of squares used, not just how many.
combine would need to track which j won at each cell in addition to the count, so the answer could be reconstructed by walking winners backward; the count itself is computed exactly the same way.

Min Sum in a Triangle Ways to Partition a Set