Posted on 2022-11-22 18:46
Uriel 阅读(44)
评论(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