Perfect Squares

Problem Description

Given an integer n, return the least number of perfect square numbers that sum to n. A perfect square is an integer that is the square of an integer.

Key Insights

• Perfect squares are non-negative integers that can be represented as k^2 where k is a non-negative integer.
• The problem can be solved using dynamic programming or breadth-first search.
• The least number of perfect squares needed to sum to n can be found by breaking down n into smaller subproblems.

Space and Time Complexity

Time Complexity: O(n * sqrt(n))
Space Complexity: O(n)

Solution

The problem can be approached using dynamic programming. We create an array dp where dp[i] represents the least number of perfect square numbers that sum to i. The main idea is to iterate through all integers from 1 to n and for each integer, check all perfect squares less than or equal to that integer. For each perfect square, we update dp[i] to reflect the minimum count needed to sum to i.

1. Initialize an array dp of size n + 1 with a default value of infinity, except for dp[0] which is 0 (since no perfect squares are needed to sum to 0).
2. Iterate through each number from 1 to n.
3. For each number, iterate through all possible perfect squares less than or equal to that number.
4. Update the dp array by taking the minimum between the current value and the value obtained by adding one to the count of perfect squares needed to sum to the remaining value (i - square).
5. The answer will be found in dp[n] at the end of the iterations.

Code Solutions