279. Perfect Squares

279

MediumOne-Dimensional Dynamic Programming1-D dynamic programmingUnbounded knapsack (fewest items)

Perfect Squares

Given an integer n, return the least number of perfect square numbers (1, 4, 9, 16, ...) that sum to n. The same square may be used multiple times.

Open official problem prompt ↗

In plain English

Compute the minimum count of perfect squares whose sum is exactly n.

Picture it like this

Making change for n using coins of denominations 1, 4, 9, 16, ... and using as few coins as possible.

Example

Input: n = 12
Output: 3
Why: 12 = 4 + 4 + 4 uses three squares; no combination of two squares sums to 12.

Constraints

1 <= n <= 10^4

Pattern lesson

See the pattern, then code

Unbounded knapsack (fewest items)

↗

One-Dimensional Dynamic Programming

Count ways or optimize a result where each state depends on earlier positions.. The fewest squares for i is one more than the fewest squares for i minus some square j*j; try every square that fits and take the minimum.

New words, made simpleKnow these before the algorithm

Perfect square: A number j*j for a positive integer j.
dp[i]: Fewest perfect squares that sum to i.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Greedy largest-square

Incorrect - e.g. 12 greedily gives 9+1+1+1=4 instead of 3.

Repeatedly subtract the biggest square that fits.

Time O(sqrt(n)) per attemptSpace O(1)

Best choiceBottom-up min DP

Correct and efficient within constraints.

dp[i] = min over squares j*j of dp[i-j*j] + 1.

Time O(n * sqrt(n))Space O(n)

The rule we keep true

Invariant

When dp[i] is finalized it equals the true minimum number of squares summing to i.

Why this is correct

Reasoning

Any optimal representation of i has a last square j*j; removing it leaves an optimal representation of i-j*j, so dp[i] = 1 + min over j of dp[i-j*j] captures the optimum by trying every possible last square.

The algorithm in three movesSay these aloud before coding

1Create dp of size n+1 with dp[0]=0 and the rest infinity

dp[4]=1 (4)

2For each amount i from 1 to n

dp[8]=2 (4+4)

3Try every square j*j <= i

dp[12]=min(dp[3]+1, dp[8]+1, dp[11]+1)=3

4Set dp[i] = min(dp[i], dp[i - j*j] + 1)

5Return dp[n]

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readi=0

2 · AskSquares summing to 0?

3 · Update statedp[0]=0

4 · ResultZero squares.

Key takeaway

dp[12] is built from dp[8]+1, giving three squares total.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3Initialize dp
dp[0]=0 (empty sum) and every other amount starts at infinity.
2
Lines 4-8Fill each amount
For amount i, try subtracting each square j*j and keep the smallest square count.
3
Lines 9Return
dp[n] holds the minimum count for the target.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

n is itself a perfect square returns 1
n=1 returns 1
By Lagrange's four-square theorem the answer is always 1, 2, 3, or 4
Small n like 2 (1+1) returns 2

Common beginner mistakes

Using a greedy largest-square strategy, which is not optimal
Off-by-one in the dp array size (need n+1)
Forgetting dp[0]=0 as the base of every chain

Check your understanding

Why does the greedy 'take the biggest square' approach fail for 12?

Perfect Squares

Perfect Squares

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in One-Dimensional Dynamic Programming