Perfect Squares
Finding the least number of perfect square numbers that sum to ( n ) can be solved using a dynamic programming approach. This problem can be thought of as finding the shortest path to reach ( n ) using perfect square numbers as steps.
Approach
 Create an Array of Squares: First, we need to identify all the perfect squares that are less than or equal to ( n ).
 Dynamic Programming Array: We’ll initialize an array
dp
of size ( n+1 ) where dp[i]
will store the least number of perfect squares that sum to ( i ).  Initialization:
dp[0]
will be 0 as zero can be represented without any perfect square.  Build Solution: Iterate from 1 to ( n ), and for each value
i
, iterate through the perfect squares. For each square sq
, update dp[i]
as the minimum between the current value and dp[isq] + 1
.  Result:
dp[n]
will store the final result.
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 class Solution:
def numSquares(self, n: int) > int:
# Generating list of squares less than or equal to n
squares = [i ** 2 for i in range(1, int(n ** 0.5) + 1)]
# Initializing dp array
dp = [float('inf')] * (n + 1)
dp[0] = 0
# Building dp array
for i in range(1, n + 1):
for sq in squares:
if i >= sq:
dp[i] = min(dp[i], dp[i  sq] + 1)
return dp[n]

Explanation
 We iterate through the numbers from 1 to ( n ), and for each number, we consider the possibility of subtracting each square.
dp[i  sq] + 1
gives us the number of perfect squares needed for the value i
considering the current square sq
. We store the minimum value in
dp[i]
, and eventually, dp[n]
will hold the result.
Key Takeaways
 Dynamic programming allows us to build the solution from the ground up.
 The time complexity of this approach is ( O(n \cdot \sqrt{n}) ).
 The space complexity is ( O(n) ), which is used to store the
dp
array.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 # @param {Integer} n
# @return {Integer}
def num_squares(n)
dp = [0] * (n + 1)
dp[0] = 1
i = 0
while i <= n
dp[i] = i
j = 1
while j*j <= i
dp[i] = [dp[i], dp[i  j*j] + 1].min
j += 1
end
i += 1
end
dp[n]
end
