279. 完全平方数

Origin: LeetCode 279

题目描述

给定一个正整数 n，找到若干个完全平方数（1, 4, 9, 16, …）使它们的和等于 n。返回最少需要多少个完全平方数。

示例

Input: n = 12 Output: 3 Explanation: 12 = 4 + 4 + 4

Input: n = 13 Output: 2 Explanation: 13 = 4 + 9

约束

• 1 <= n <= 10

关键信息

• 完全平方数可无限次使用 → 完全背包
• 求最少个数 → 和 HackerRank 第 37 题完全一样的框架
• dp[i] = min(dp[i], dp[i - jj] + 1)，jj 是完全平方数

Resolution

我的解法

function numSquares(n: number): number {
    // dp[i] = min(dp[i -j*j] + 1, dp[i])
    const dp = Array.from({ length: n + 1 }, (v, k) => k)
    for (let i = 1; i <= n; i++) {
        let min = i
        for (let j = 0; j * j <= i; j++) {
            min = Math.min(dp[i - j * j] + 1, min)
        }
        dp[i] = min
    }
    return dp[n]
}

初始化用 k（最多用 i 个 1 凑齐），比 Infinity 更直觉。j 从 0 开始，j=0 时 dp[i]+1 比 dp[i] 大会被 min 忽略，不影响正确性。

标准解法（Infinity 初始化）

function numSquares(n: number): number {
    const dp: number[] = Array.from({ length: n + 1 }, () => Infinity)
    dp[0] = 0
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j * j <= i; j++) {
            dp[i] = Math.min(dp[i], dp[i - j * j] + 1)
        }
    }
    return dp[n]
}

Infinity 初始化更通用，j 从 1 开始语义更清晰。两种初始化都对。

解题思路

完全背包 / 硬币找零，和 HackerRank 第 37 题完全一样的框架。硬币就是完全平方数 1, 4, 9, 16…，target 就是 n。

• dp[i] = 凑齐 i 所需的最少完全平方数个数
• dp[0] = 0，其他初始化 Infinity
• 对每个 i，遍历 j（jj <= i），dp[i] = min(dp[i], dp[i - jj] + 1)

j 从 1 开始，j*j <= i 递增。比如 i=12：j=1(1)、j=2(4)、j=3(9)。dp[12] = min(dp[11]+1, dp[8]+1, dp[3]+1) = min(3+1, 2+1, 3+1) = 3。

复杂度

• 时间：O(n × √n)，内层循环最多 √n 次
• 空间：O(n)