LeetCode 熱題 100 | 279. 完全平方數
大家好，今天我們來解決一道經典的動態規劃問題——完全平方數。這道題在 LeetCode 上被標記為中等難度，要求找到和為給定整數 n 的完全平方數的最少數量。
問題描述
給定一個整數 n，返回和為 n 的完全平方數的最少數量。
示例 1：
輸入：n = 12
輸出：3
解釋：12 = 4 + 4 + 4
示例 2：
輸入：n = 13
輸出：2
解釋：13 = 4 + 9
提示：
1 <= n <= 10^4
解題思路
核心思想
-
動態規劃：
- 使用動態規劃（DP）來解決這個問題。
- 定義
dp[i]為和為i的完全平方數的最少數量。 - 狀態轉移方程為：
[
dp[i] = \min_{j^2 \leq i} (dp[i - j^2] + 1)
]
其中，j^2是小于等于i的完全平方數。
-
初始化：
dp[0] = 0，因為和為 0 的完全平方數的最少數量是 0。dp[1] = 1，因為和為 1 的完全平方數的最少數量是 1。
-
遍歷：
- 從 2 到
n遍歷，對于每個i，找到所有小于等于i的完全平方數j^2，并更新dp[i]。
- 從 2 到
狀態轉移方程的推導
1. 定義狀態
dp[i] 表示和為 i 的完全平方數的最少數量。
2. 狀態轉移
假設我們已經知道了所有小于 i 的 dp 值，現在需要計算 dp[i]。為了得到和為 i 的完全平方數的最少數量，我們可以嘗試以下方法：
- 選擇一個完全平方數：選擇一個完全平方數
j^2，使得j^2 <= i。 - 計算剩余部分：如果選擇了
j^2，那么剩下的部分就是i - j^2。 - 遞歸關系：因此，
dp[i]可以表示為dp[i - j^2] + 1，其中+1表示我們選擇了一個完全平方數j^2。
3. 選擇最優解
由于 j^2 有多種可能（例如 1, 4, 9, 16 等），我們需要在所有可能的 j^2 中選擇一個使得 dp[i - j^2] + 1 最小的值。因此，狀態轉移方程為：
[
dp[i] = \min_{j^2 \leq i} (dp[i - j^2] + 1)
]
詳細解釋
假設我們正在計算 dp[12]，即和為 12 的完全平方數的最少數量。我們可以嘗試以下完全平方數：
-
選擇
j^2 = 1：- 剩下的部分是
12 - 1 = 11。 - 因此，
dp[12] = dp[11] + 1。
- 剩下的部分是
-
選擇
j^2 = 4：- 剩下的部分是
12 - 4 = 8。 - 因此，
dp[12] = dp[8] + 1。
- 剩下的部分是
-
選擇
j^2 = 9：- 剩下的部分是
12 - 9 = 3。 - 因此，
dp[12] = dp[3] + 1。
- 剩下的部分是
-
選擇
j^2 = 16：- 但
16 > 12，所以不能選擇。
- 但
我們需要在這些選擇中找到最小值：
[
dp[12] = \min(dp[11] + 1, dp[8] + 1, dp[3] + 1)
]
Python代碼實現
class Solution(object):def numSquares(self, n):""":type n: int:rtype: int"""dp = [0] * (n + 1)dp[0] = 0dp[1] = 1for i in range(2, n + 1):temp = []j = 1while j * j <= i:temp.append(dp[i - j * j])j += 1dp[i] = min(temp) + 1return dp[n]
代碼解析
-
初始化：
dp數組初始化為長度為n + 1的列表，所有值初始化為 0。dp[0] = 0，因為和為 0 的完全平方數的最少數量是 0。dp[1] = 1，因為和為 1 的完全平方數的最少數量是 1。
-
狀態轉移：
- 遍歷從 2 到
n的每個整數i。 - 對于每個
i，找到所有小于等于i的完全平方數j^2。 - 將
dp[i - j^2]的值存儲到臨時列表temp中。 - 更新
dp[i]為min(temp) + 1，表示選擇一個完全平方數j^2后的最小值。
- 遍歷從 2 到
-
返回結果：
- 最終結果存儲在
dp[n]中。
- 最終結果存儲在
復雜度分析
- 時間復雜度：O(n * sqrt(n))，其中
n是給定的整數。對于每個i，需要遍歷所有小于等于i的完全平方數。 - 空間復雜度：O(n)，使用了長度為
n + 1的dp數組。
示例運行
示例 1
輸入：n = 12
輸出：3
解釋：12 = 4 + 4 + 4
示例 2
輸入：n = 13
輸出：2
解釋：13 = 4 + 9
總結
通過動態規劃的方法，我們可以高效地解決完全平方數問題。狀態轉移方程 dp[i] = \min_{j^2 \leq i} (dp[i - j^2] + 1) 確保了我們能夠找到和為 i 的完全平方數的最少數量。希望這篇題解對大家有所幫助，如果有任何問題，歡迎在評論區留言討論！
關注我，獲取更多算法題解和編程技巧！
