Perfect Squares — Solution

Problem

Given a positive integer, find the minimum number of perfect square numbers (1, 4, 9, 16, …) whose sum equals it. You may reuse the same perfect square as many times as you like.

• Input: n = 12
• Output: 3
• Explanation: 12 = 4 + 4 + 4, and no two squares can reach 12 (4+9=13, not 12)

Another example: n = 13 → 2 because 13 = 4 + 9.

Intuition

Every number can be "built" by adding one perfect square to a smaller number. If we already know the minimum squares needed for every number below n, we can compute the answer for n by trying each perfect square we could "add last" and taking the minimum. This is a standard bottom-up DP — the answer for i depends only on previously computed answers.

Solution — Bottom-Up DP

Build a dp table where dp[i] holds the minimum number of perfect squares that sum to i. Start with dp[0] = 0 (zero squares needed to reach zero), then fill left to right. For each position i, try subtracting every perfect square that fits and record the best result.

1. Precompute all perfect squares up to n: 1, 4, 9, …, floor(√n)².
2. Allocate dp of size n + 1, initialized to infinity; set dp[0] = 0.
3. For each i from 1 to n:
   • For each perfect square sq where sq ≤ i:
     • dp[i] = min(dp[i], dp[i - sq] + 1)
4. Return dp[n].

1def numSquares(n: int) -> int:
2    squares = []
3    j = 1
4    while j * j <= n:
5        squares.append(j * j)
6        j += 1
7
8    dp = [float('inf')] * (n + 1)
9    dp[0] = 0  # base case: zero squares needed to reach zero
10
11    for i in range(1, n + 1):
12        for sq in squares:
13            if sq > i:
14                break  # all remaining squares are too large
15            dp[i] = min(dp[i], dp[i - sq] + 1)
16
17    return dp[n]

Time: O(n √n) — for each of the n positions we try up to √n perfect squares.

Space: O(n) — the dp array stores one value per integer from 0 to n.

Complexity Summary

Common Mistakes

• Initializing dp[0] = 1 instead of 0 — the base case must be 0 because zero squares are needed to sum to zero; every other entry derives from this, so an incorrect base corrupts the entire table.
• Initializing dp[i] = 0 instead of infinity for i > 0 — min() against 0 always returns 0, so every dp entry stays zero and the function returns 0 for all inputs.
• Using sq < i instead of sq <= i as the break condition — this skips the case where i itself is a perfect square (e.g., dp[4] never tries sq = 4 and returns 4 instead of 1).
• Treating this like 0/1 knapsack and using each square at most once — perfect squares can be reused (12 = 4 + 4 + 4), so an approach that marks a square as "used" will give wrong answers for inputs that require repetition.
• Regenerating the squares list inside the outer loop — precomputing once outside is clearer and avoids redundant work; generating fresh on each iteration of i doesn't affect correctness but obscures the algorithm's structure.

Related Problems

• coin-change — identical unbounded knapsack framing; find the minimum number of coins to reach a target amount
• climbing-stairs — simpler DP where each position depends on 1 or 2 prior entries; same "build from subproblems" structure
• word-break — DP checking whether a target can be formed from elements in a dictionary; same "can I reach position i?" framing
• triangle — bottom-up DP that fills a table from the base row upward, reinforcing the same left-to-right fill technique
• minimum-path-sum — extends the same principle to two dimensions where each cell depends on the cell above and to the left