Perfect Squares: Dynamic Programming with Square Numbers

May 14, 20264 min read

leetcodeproblemmediumdynamic-programming

Given an integer n, find the least number of perfect square numbers (1, 4, 9, 16, ...) that sum to n. For example, if n = 12, the answer is 3 because 12 = 4 + 4 + 4. If n = 13, the answer is 2 because 13 = 4 + 9.

This is LeetCode 279: Perfect Squares, and once you see how it connects to Coin Change, you will recognize it as the same DP pattern with a different set of "denominations."

Completed DP table for n = 12. dp[12] = 3, meaning the least number of perfect squares summing to 12 is 3 (4 + 4 + 4).

Why this problem matters

If you have solved Coin Change, this problem is essentially the same thing. Instead of arbitrary coin denominations like [1, 5, 10, 25], your "coins" are the perfect squares: 1, 4, 9, 16, 25, and so on. The DP structure is identical. The recurrence is identical. Only the set of options at each step changes.

This reinforces the unbounded knapsack DP pattern. You are choosing from a set of items (perfect squares) that you can use repeatedly, trying to minimize the count needed to reach a target sum. Recognizing this connection means you do not need to "learn" this problem separately. You already know how to solve it.

The approach: DP table where dp[i] = min squares summing to i

Define dp[i] as the minimum number of perfect squares that sum to i. The recurrence is:

dp[0] = 0 (zero squares needed to sum to zero)
For each i from 1 to n, try subtracting every perfect square j*j where j*j <= i: set dp[i] = min(dp[i], dp[i - j*j] + 1)
Initialize every cell to infinity (meaning "not yet computed")

At each position, you ask: "If I use one square of size j*j, how many squares did I need for the remainder i - j*j?" Then you pick the option that gives the smallest total.

def num_squares(n):
    dp = [float('inf')] * (n + 1)
    dp[0] = 0
    for i in range(1, n + 1):
        j = 1
        while j * j <= i:
            dp[i] = min(dp[i], dp[i - j * j] + 1)
            j += 1
    return dp[n]

Practice this problem with spaced repetition

Step-by-step walkthrough

Base case: dp[0] = 0

Zero squares needed to sum to 0.

dp[1]: Try 1*1=1. dp[1-1]+1 = dp[0]+1 = 1. dp[1] = 1

Only 1*1 fits. One square needed.

dp[2]: Try 1*1. dp[1]+1 = 2. dp[2] = 2

Only 1*1 fits. Two squares: 1+1.

dp[3]: Try 1*1. dp[2]+1 = 3. dp[3] = 3

Only 1*1 fits. Three squares: 1+1+1.

dp[4]: Try 1*1 -> dp[3]+1=4. Try 2*2 -> dp[0]+1=1. dp[4] = 1

Using 2*2=4 lands us at dp[0]=0. Just 1 square needed: 4 itself.

dp[5]: Try 1*1 -> dp[4]+1=2. Try 2*2 -> dp[1]+1=2. dp[5] = 2

Both paths give 2. Best: 4+1 or 1+4. Two squares either way.

dp[6]: Try 1*1 -> dp[5]+1=3. Try 2*2 -> dp[2]+1=3. dp[6] = 3

Both options give 3 squares. For example: 4+1+1.

The key insight at every step: you try every perfect square that fits and pick the minimum. For dp[4], using 2*2 jumps straight back to dp[0], giving you just 1 square. That is better than using four 1s. For dp[5], you try 1*1 (lands at dp[4] = 1, total 2) and 2*2 (lands at dp[1] = 1, total 2). Both give 2, so dp[5] = 2.

The pattern continues all the way up to your target. At dp[12], you would try 1*1 (from dp[11] = 3, total 4), 2*2 (from dp[8] = 2, total 3), and 3*3 (from dp[3] = 3, total 4). The winner is 2*2 from dp[8], giving dp[12] = 3.

The connection to Coin Change

This is literally Coin Change where your coins are [1, 4, 9, 16, 25, ...]. Compare the two recurrences side by side:

Coin Change: dp[i] = min(dp[i - coin] + 1) for each coin in the set
Perfect Squares: dp[i] = min(dp[i - j*j] + 1) for each j where j*j <= i

Same structure, same base case, same initialization. The only difference is how you generate the list of "denominations." In Coin Change, the coins are given to you. In Perfect Squares, the coins are all squares up to sqrt(n).

If you have already internalized Coin Change, you can write this solution in under two minutes. That is the power of learning patterns rather than memorizing individual problems.

Complexity analysis

Approach	Time	Space
Bottom-up DP	O(n * sqrt(n))	O(n)
BFS	O(n * sqrt(n))	O(n)

The outer loop runs n times. The inner loop (trying each square) runs at most sqrt(n) times per iteration, since squares grow quadratically. Total: O(n * sqrt(n)).

The BFS approach treats this as a shortest-path problem: start at n, subtract squares to reach neighbors, and find the shortest path to 0. It has the same asymptotic complexity but uses more overhead in practice due to queue management.

Build your pattern library with CodeBricks

The building blocks

This problem belongs to the unbounded knapsack DP pattern. You have a set of items (perfect squares) that you can use any number of times, and you want to minimize the count to reach a target. The same pattern appears in:

Coin Change (LeetCode 322): exact same structure, just different denominations
Minimum Cost for Tickets (LeetCode 983): denominations are ticket durations (1, 7, 30 days)
Word Break (LeetCode 139): at each position, try every "piece" (word) that fits

Once you recognize this shared structure, all of these problems become variations on a single theme.

Edge cases to watch for

n is itself a perfect square (answer is 1)
n = 1 (answer is 1)
n = 2 (answer is 2: 1+1)
Large n (up to 10000 per constraints)

From understanding to recall

You can follow this walkthrough and understand every step. But could you write the solution from scratch in an interview next week? Understanding and recall are different skills. Spaced repetition bridges that gap. You revisit the perfect squares DP table at increasing intervals, write the recurrence from memory each time, and after a few reps the pattern is automatic. Since this shares the same building block as Coin Change, drilling one reinforces the other.

Coin Change - The exact same DP pattern with arbitrary coin denominations
Climbing Stairs - Simpler DP with fixed step sizes, same core idea
Word Break - Another DP where you try all valid "pieces" at each position

Try CodeBricks free