How do you approach Perfect Squares?

dp[i] is the fewest squares summing to i.

What are common mistakes on Perfect Squares?

Iterating the dimensions in an order that reads a cell before it has been written. Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input. Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.

gitGood.dev

← Back to problems

Perfect Squares

MediumAlgorithms

Description

Given an integer n, return the least number of perfect-square numbers (1, 4, 9, 16, ...) that sum to n.

Example 1

Input: n = 12

Output: 3

Explanation: 12 = 4 + 4 + 4.

Example 2

Input: n = 13

Output: 2

Explanation: 13 = 4 + 9.

Constraints

- 1 <= n <= 10^4

Perfect Squares: approach, complexity and pitfalls

A medium dynamic programming problem, graded against 7 test cases (5 of them hidden).

The pattern: Dynamic Programming

Overlapping subproblems solved once and reused - the pattern candidates fear most.

Reach for it when you see: "Number of ways", "minimum/maximum cost", or a recursion that recomputes the same state.

If you are stuck

Show the 2-step hint ladder

dp[i] is the fewest squares summing to i.
For each i, try subtracting every square j*j <= i.

The optimal approach

Show the approach: The approach

Unbounded coin-change with square coins. `dp[i] = 1 + min over j of dp[i - j²]` for `j² <= i`. Build from 1 to n; `dp[n]` is the minimum count.

Time: O(n·√n). Space: O(n).

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

Common Dynamic Programming mistakes

These apply to the pattern as a whole, not just this problem.

Iterating the dimensions in an order that reads a cell before it has been written.
Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input.
Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.