update 279.完全平方数: 提供新的初始化方法

EnzoSeason · EnzoSeason · commit 5e68f30728cb · 2021-06-27T17:40:11.000+02:00
diff --git a/problems/0279.完全平方数.md b/problems/0279.完全平方数.md
@@ -214,8 +214,26 @@ class Solution:
         return dp[n]
 ```
 
+Python3:
+```python
+class Solution:
+    def numSquares(self, n: int) -> int:
+        # 初始化
+        # 组成和的完全平方数的最多个数，就是只用1构成
+        # 因此，dp[i] = i
+        dp = [i for i in range(n + 1)]
+        # dp[0] = 0 无意义，只是为了方便记录特殊情况:
+        # n本身就是完全平方数，dp[n] = min(dp[n], dp[n - n] + 1) = 1
+
+        for i in range(1, n): # 遍历物品
+            if i * i > n:
+                break
+            num = i * i
+            for j in range(num, n + 1): # 遍历背包
+                dp[j] = min(dp[j], dp[j - num] + 1)
 
-
+        return dp[n]
+```
 
 Go：
 ```go
