Introduction

The problem is: given a positive integer n, find the minimum number of perfect squares whose sum is exactly n. The most practical algorithmic answer is dynamic programming, although breadth-first search and number-theory shortcuts are also useful ways to think about the same problem.

The Dynamic Programming Recurrence

Let dp[i] be the minimum number of perfect squares that sum to i.

Then:

• 'dp[0] = 0'
• for every i > 0, try every square s such that s <= i
• choose the best previous state dp[i - s] + 1

That gives the recurrence:

• 'dp[i] = min(dp[i - s] + 1) over all perfect squares s <= i'

This works because the final square used in an optimal decomposition must be some square s, and the rest of the sum must optimally form i - s.

A Runnable Python Implementation

1import math
2
3
4def min_num_squares(n):
5    dp = [0] + [float("inf")] * n
6
7    for i in range(1, n + 1):
8        j = 1
9        while j * j <= i:
10            square = j * j
11            dp[i] = min(dp[i], dp[i - square] + 1)
12            j += 1
13
14    return dp[n]
15
16print(min_num_squares(12))
17print(min_num_squares(13))

Output:

3
2

Explanation:

• '12 = 4 + 4 + 4, so the answer is 3'
• '13 = 9 + 4, so the answer is 2'

Why This Works

The DP table builds solutions from smaller values upward. By the time you compute dp[i], every dp[i - square] is already known.

That means the algorithm systematically checks every valid last-square choice and keeps the best one.

This is a classic optimal-substructure problem:

• the best solution for i depends on best solutions for smaller values
• those smaller subproblems repeat often

That is exactly the kind of structure dynamic programming is meant for.

Time And Space Complexity

The number of squares less than or equal to n is about sqrt(n), and for each i you try all such squares up to i.

So the complexity is:

• time: O(n * sqrt(n))
• space: O(n)

For many interview and programming-contest inputs, this is efficient enough and easy to reason about.

A Graph Interpretation

You can also see the problem as a shortest-path or BFS problem.

Think of each number as a node. From x, you can move to x - 1^2, x - 2^2, x - 3^2, and so on as long as the result stays nonnegative. The answer is the shortest path from n to 0.

A BFS implementation makes that idea explicit.

1from collections import deque
2
3
4def min_num_squares_bfs(n):
5    squares = [i * i for i in range(1, int(n ** 0.5) + 1)]
6    queue = deque([(n, 0)])
7    seen = {n}
8
9    while queue:
10        value, steps = queue.popleft()
11        if value == 0:
12            return steps
13
14        for square in squares:
15            if square > value:
16                break
17            nxt = value - square
18            if nxt not in seen:
19                seen.add(nxt)
20                queue.append((nxt, steps + 1))

This returns the same answer, but the DP version is usually the more standard implementation.

Number Theory Gives Strong Bounds

There is also useful theory behind the problem.

Lagrange's four-square theorem says every positive integer can be written as the sum of at most four perfect squares. That means the answer is always in:

• '1'
• '2'
• '3'
• '4'

So you never need five or more squares.

That theorem is mathematically powerful, but it does not by itself give the simplest implementation for arbitrary n. Dynamic programming is still the most straightforward coding answer.

Greedy Is Not Reliable

A tempting but incorrect idea is always taking the largest square possible first.

For example, with 12:

• greedy picks 9
• remainder is 3
• total becomes 9 + 1 + 1 + 1, which uses 4 squares

But the optimal answer is 4 + 4 + 4, which uses only 3.

So this is not a greedy problem.

Common Pitfalls

• Using a greedy largest-square-first strategy and assuming it is optimal.
• Forgetting that the answer is a minimum over all valid last-square choices.
• Recomputing subproblems recursively without memoization and getting slow exponential behavior.
• Misunderstanding the problem as asking for the number of ways rather than the minimum count.
• Ignoring simple mathematical bounds such as the fact that four squares always suffice.

Summary

• The problem asks for the minimum count of perfect squares that sum to n.
• Dynamic programming gives a clean O(n * sqrt(n)) solution.
• BFS provides an equivalent shortest-path viewpoint.
• Greedy selection of the largest square is not always optimal.
• Number theory guarantees the answer is never greater than four.