Perfect Squares

279. Perfect Squares

Solution

1. _dp stores the least number of perfect squares for index.

2. When len(_dp) < n, we can update it using the previous results.

3. For i, it can use results from _dp[i - perfect squares] + 1.

4. Select the minimum of all results, it is the result for _dp[i].

_dp = [0]
        
def numSquares(self, n):
    """
    :type n: int
    :rtype: int
    """
    
    dp = self._dp
    while len(dp) <= n:
        dp += min(dp[-i*i] for i in range(1, int(len(dp)**0.5+1))) + 1,
    return dp[n]