LeetCode 完美平方數：動態規劃與數學定理雙重解法

問題描述

給定正整數 n，求最少多少個完全平方數（1, 4, 9, 16...）之和等於 n。例如 n=12 答案 3 (4+4+4)；n=13 答案 2 (4+9)。

動態規劃解法

定義 dp[i] 為組成 i 所需最少平方數個數。初始化 dp[j*j] = 1。對於每個 i，枚舉小於 i 的平方數 k²，轉移 dp[i] = min(dp[i], dp[i - k*k] + 1)。時間 O(n√n)，空間 O(n)。

數學解法：四平方和定理

根據 Lagrange 四平方定理，答案只能是 1, 2, 3, 4。判斷步驟：

1. 若 n 為完全平方數，返回 1。
2. 若 n 滿足 n = 4^a * (8b + 7)（Legendre 三平方定理），返回 4。
3. 枚舉 i=1..√n，若 n - i*i 為平方數，返回 2。
4. 否則返回 3。

時間 O(√n)，空間 O(1)，極快。

代碼實現

class Solution {
    bool is_square(int n) {
        int r = sqrt(n);
        return r*r == n;
    }
public:
    int numSquares(int n) {
        if (is_square(n)) return 1;
        int m = n;
        while (m % 4 == 0) m >>= 2;
        if (m % 8 == 7) return 4;
        for (int i = 1; i*i <= n; ++i)
            if (is_square(n - i*i)) return 2;
        return 3;
    }
};

總結

數學解法優雅高效，面試中展示數論功力加分項；DP 解法通用易懂，適合無數論背景場景。