Ural 1073 Square Country：完全背包求最少平方數之和

Ural 1073「Square Country」：給定 N (≤ 60000)，求表示為最少幾個完全平方數之和（如 344 = 18² + 6² + 2²，答案 3）。本文解析完全背包 DP 解法，並提及四平方和定理優化。

問題建模：完全背包

• 物品：所有平方數 i² (i=1..244)，因 245²=60025 > 60000。
• 背包容量：N
• 每個物品價值 = 1（計數），可無限選取。
• 目標：恰裝滿容量 N，最小化總價值（個數）。

DP 狀態與轉移

dp[j] = 湊成和 j 所需最少平方數個數
dp[0] = 0
dp[j] = min(dp[j], dp[j - i²] + 1)  for all i² ≤ j

代碼實現（C++）

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 60000;
const int INF = 0x3f3f3f3f;
int dp[MAXN + 1];

int main() {
    // 預計算所有答案
    fill(dp, dp + MAXN + 1, INF);
    dp[0] = 0;
    for (int i = 1; i * i <= MAXN; ++i) {
        int sq = i * i;
        for (int j = sq; j <= MAXN; ++j) {
            dp[j] = min(dp[j], dp[j - sq] + 1);
        }
    }

    int n;
    while (scanf("%d", &n) == 1) {
        printf("%d\n", dp[n]);
    }
    return 0;
}

四平方和定理優化（O(1) 查詢）

拉格朗日四平方和定理：任何自然數可表示為 ≤4 個平方數之和。結合勒讓德三平方定理可 O(1) 判斷答案：

1. 若 n 為完全平方數 → 1
2. 若 n = 4^a (8b + 7) → 4（勒讓德條件）
3. 若 n 可寫為兩個平方數之和 → 2
4. 否則 → 3

int minSquares(int n) {
    // 1. 完全平方數
    int r = sqrt(n);
    if (r * r == n) return 1;
    // 2. 檢查 4^a(8b+7)
    int m = n;
    while (m % 4 == 0) m /= 4;
    if (m % 8 == 7) return 4;
    // 3. 兩個平方數之和
    for (int i = 1; i * i <= n; ++i) {
        int j2 = n - i * i;
        int j = sqrt(j2);
        if (j * j == j2) return 2;
    }
    return 3;
}

複雜度對比

總結

本題是完全背包的標準應用。N=60000 時 DP 預計算極快（~0.03s），代碼簡單通用。若 N 更大或單次查詢，四平方和定理提供 O(√N) 甚至 O(1) 解法。面試中建議先給出 DP 通解，再展開數學優化作為進階討論。