給定一個(gè)數(shù)n，問它最少由幾個(gè)平方數(shù)加和而成（可以重復(fù)使用）
先預(yù)處理算出比n小的平方數(shù)，再用DP思想，直接O(n^2)的話python會(huì)TLE，所以第二重循環(huán)需要優(yōu)化為logn
借鑒Discussion的思路：https://leetcode.com/problems/perfect-squares/discuss/2837770/Python3-DP-with-Detailed-Explanations-O(-n-sqrt(n)-)-not-TLE
第二重循環(huán)只要遍歷預(yù)處理的平方數(shù)的數(shù)組
另一個(gè)小trick：把dp[0]寫作class變量可以節(jié)省很多時(shí)間，如果寫在numSquares函數(shù)內(nèi)依舊TLE
“Make dp a class variable, so that it will not rebuild dp from 0 for different testing cases.”
1 #279
2 #Runtime: 309 ms
3 #Memory Usage: 13.3 MB
4
5 class Solution(object):
6 dp = [0]
7 def numSquares(self, n):
8 """
9 :type n: int
10 :rtype: int
11 """
12 sq_num = [i**2 for i in range(1, int(sqrt(n)) + 1)]
13 while len(self.dp) < n + 1:
14 t = 10001
15 for i in sq_num:
16 if i > len(self.dp):
17 break
18 t = min(t, 1 + self.dp[-i])
19 self.dp.append(t)
20 return self.dp[n]
21