Posted on 2022-11-22 18:46
Uriel 閱讀(59)
評論(0) 編輯 收藏 引用 所屬分類:
DP 、
閑來無事重切Leet Code
給定一個數n，問它最少由幾個平方數加和而成（可以重復使用）
先預處理算出比n小的平方數，再用DP思想，直接O(n^2)的話python會TLE，所以第二重循環需要優化為logn
借鑒Discussion的思路：https://leetcode.com/problems/perfect-squares/discuss/2837770/Python3-DP-with-Detailed-Explanations-O(-n-sqrt(n)-)-not-TLE
第二重循環只要遍歷預處理的平方數的數組
另一個小trick：把dp[0]寫作class變量可以節省很多時間，如果寫在numSquares函數內依舊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