248. Perfect Squares
A perfect square is an integer that equals some integer times itself: 1, 4, 9, 16, 25, …
Your function receives a single positive integer n and must return the minimum count of perfect squares whose sum is exactly n. You may reuse the same square as many times as you like.
For instance, 12 needs three terms (4 + 4 + 4) — writing it as 9 + 1 + 1 + 1 also works but spends four — while 13 needs only two (4 + 9).
Example 1:
Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4 uses three squares, and no combination of one or two squares reaches 12.
Example 2:
Input: n = 13
Output: 2
Explanation: 13 = 4 + 9, so two squares suffice.
Constraints:
- 1 ≤ n ≤ 10⁴
Hints:
Think in terms of subproblems: if the last square you spend is s², the rest of the sum must build n − s² optimally. So answer(n) = 1 + min over all s² <= n of answer(n − s²).
That recurrence is a textbook 1-D dynamic program: fill dp[0..n] left to right, where dp[i] = 1 + min(dp[i − s²]) over every square s² <= i. About √i choices per cell gives O(n·√n) total.
You can also see it as a shortest-path search: numbers are nodes, and an edge subtracts one square. BFS from n finds the fewest edges to reach 0 — the answer is the depth.
For the math-inclined: Lagrange's four-square theorem caps every answer at 4, and Legendre's three-square theorem tells you exactly when the answer is 4 (n of the form 4^a(8b+7)). Checking 1 and 2 directly then decides everything in O(√n).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: n = 12
Expected output: 3