Approach Summary
dp[i] = minimum squares summing to i. For each i, try all squares ≤ i: dp[i] = min(dp[i - sq] + 1). dp[0] = 0.
How to Recognize This Pattern
- "Fewest perfect squares summing to n"
- Unbounded knapsack with square numbers as items
Complexity Analysis
Time Complexity
O(n √n)
Space Complexity
O(n)
Tags
Math Dynamic Programming BFS