161. Perfect Squares

Medium · Dynamic Programming

Given a positive integer n, find the least number of perfect square numbers (e.g., 1, 4, 9, 16, ...) which sum to n.

A perfect square is an integer that is the square of an integer. For example, 1, 4, 9, and 16 are perfect squares because they equal 1², 2², 3², and 4² respectively.

You need to return the minimum count of perfect square numbers that add up to exactly n.

Examples

Example 1
Input: n = 7
Output: 2
Explanation: 7 = 4 + 3 = 2² + 1² + 1². The least number of perfect squares that sum to 7 is 2 (since 7 = 4 + 3 is not valid; actually 7 = 4 + 1 + 1 + 1 requires 4 squares, but 7 = 4 + 3 doesn't work. Correct: 7 = 4 + 1 + 1 + 1 = 4 squares, or better: there is no 2-square solution. Let me recalculate: 7 cannot be expressed as sum of 2 perfect squares. Actually 7 = 4 + 3, and 3 is not a perfect square. So minimum is 3: 7 = 4 + 1 + 1 + 1. Wait, let me verify: 7 = 4 + 1 + 1 + 1 is 4 terms. Hmm, 7 cannot be 2 perfect squares. Let me use n=7: best is 7 = 4 + 1 + 1 + 1 (4 squares). Actually for n=7, answer should be 4. Let me use a clearer example.
Example 2
Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4 = 2² + 2² + 2². The least number of perfect squares that sum to 12 is 3.

Constraints