279. Perfect Squares — Step-by-Step Visualization

Algorithm Pattern

Unbounded Knapsack (Coin Change variant)

Key Idea

Treat perfect squares as 'coins'. dp[i] = min squares that sum to i. For each i, try every j where j² ≤ i and take dp[i - j²] + 1.

Step-by-Step Approach

1. Initialize dp[0] = 0, dp[1..n] = ∞.
2. For each i from 1 to n:
3. Try every j = 1, 2, … while j² ≤ i.
4. dp[i] = min(dp[i], dp[i - j²] + 1).
5. Return dp[n].

Common Gotchas

• Inner loop iterates j (not j²) — increment j by 1, stopping when j*j > i.
• This is identical to Coin Change where coins are [1, 4, 9, 16, …].