LeetCode中完全平方數的示例分析

LeetCode中完全平方數的示例分析

在LeetCode中，完全平方數（Perfect Squares）是一個常見的算法問題。這類問題通常要求我們找到一個數的最少完全平方數的和，或者判斷一個數是否可以表示為若干個完全平方數的和。本文將通過幾個示例，詳細分析這類問題的解決思路和算法實現。

問題描述

LeetCode中的完全平方數問題通常有以下幾種形式：

1. 最少完全平方數的和：給定一個正整數 n，找到最少的完全平方數的和等于 n。
2. 判斷是否為完全平方數：給定一個正整數 n，判斷 n 是否可以表示為若干個完全平方數的和。

本文主要關注第一種問題，即找到最少的完全平方數的和等于 n。

示例分析

示例 1：n = 12

問題描述：給定 n = 12，找到最少的完全平方數的和等于 12。

分析：

首先，我們需要找到所有小于等于 12 的完全平方數。這些完全平方數包括：1, 4, 9。

接下來，我們可以使用動態規劃（Dynamic Programming, DP）來解決這個問題。我們定義一個數組 dp，其中 dp[i] 表示組成數字 i 所需的最少完全平方數的個數。

動態規劃步驟：

1. 初始化 dp 數組，長度為 n + 1，初始值為無窮大（表示無法組成），dp[0] = 0。
2. 對于每個 i 從 1 到 n，遍歷所有小于等于 i 的完全平方數 j，更新 dp[i] = min(dp[i], dp[i - j] + 1)。

具體實現：

def numSquares(n):
    dp = [float('inf')] * (n + 1)
    dp[0] = 0
    for i in range(1, n + 1):
        j = 1
        while j * j <= i:
            dp[i] = min(dp[i], dp[i - j * j] + 1)
            j += 1
    return dp[n]

結果：

對于 n = 12，dp 數組的最終狀態為：

dp = [0, 1, 2, 3, 1, 2, 3, 4, 2, 1, 2, 3, 3]

因此，dp[12] = 3，表示 12 可以由 4 + 4 + 4 或 9 + 1 + 1 + 1 組成，最少需要 3 個完全平方數。

示例 2：n = 13

問題描述：給定 n = 13，找到最少的完全平方數的和等于 13。

分析：

同樣地，我們首先找到所有小于等于 13 的完全平方數：1, 4, 9。

動態規劃步驟：

1. 初始化 dp 數組，長度為 14，初始值為無窮大，dp[0] = 0。
2. 對于每個 i 從 1 到 13，遍歷所有小于等于 i 的完全平方數 j，更新 dp[i] = min(dp[i], dp[i - j] + 1)。

具體實現：

def numSquares(n):
    dp = [float('inf')] * (n + 1)
    dp[0] = 0
    for i in range(1, n + 1):
        j = 1
        while j * j <= i:
            dp[i] = min(dp[i], dp[i - j * j] + 1)
            j += 1
    return dp[n]

結果：

對于 n = 13，dp 數組的最終狀態為：

dp = [0, 1, 2, 3, 1, 2, 3, 4, 2, 1, 2, 3, 3, 2]

因此，dp[13] = 2，表示 13 可以由 9 + 4 組成，最少需要 2 個完全平方數。

示例 3：n = 18

問題描述：給定 n = 18，找到最少的完全平方數的和等于 18。

分析：

首先，找到所有小于等于 18 的完全平方數：1, 4, 9, 16。

動態規劃步驟：

1. 初始化 dp 數組，長度為 19，初始值為無窮大，dp[0] = 0。
2. 對于每個 i 從 1 到 18，遍歷所有小于等于 i 的完全平方數 j，更新 dp[i] = min(dp[i], dp[i - j] + 1)。

具體實現：

def numSquares(n):
    dp = [float('inf')] * (n + 1)
    dp[0] = 0
    for i in range(1, n + 1):
        j = 1
        while j * j <= i:
            dp[i] = min(dp[i], dp[i - j * j] + 1)
            j += 1
    return dp[n]

結果：

對于 n = 18，dp 數組的最終狀態為：

dp = [0, 1, 2, 3, 1, 2, 3, 4, 2, 1, 2, 3, 3, 2, 3, 4, 1, 2, 2]

因此，dp[18] = 2，表示 18 可以由 9 + 9 組成，最少需要 2 個完全平方數。

總結

通過以上示例分析，我們可以看到，動態規劃是解決完全平方數問題的有效方法。通過定義 dp 數組并逐步更新，我們可以找到組成給定數字 n 所需的最少完全平方數的個數。這種方法的時間復雜度為 O(n * sqrt(n))，空間復雜度為 O(n)，適用于大多數情況。

在實際應用中，我們還可以結合數學方法（如四平方和定理）來進一步優化算法，但這超出了本文的范圍。希望本文的示例分析能夠幫助讀者更好地理解完全平方數問題的解決思路。