LC279　完全平方数¶

中等通过率 68.3%python3核心代码模式动态规划样例通过牛客 AC广度优先搜索数学动态规划背包问题完全背包

牛客原题　源码

讲解章节：背包问题

一句话

把平方数当成面值无限供应的硬币，做一遍完全背包求最少个数。

解题思路¶

这题考什么¶

「用若干个数凑出目标值，每个数可以重复使用，求最少个数」正是完全背包的最小化形态，见背包问题。这题的物品表是现成的：所有不超过 n 的完全平方数 1, 4, 9, ..., k*k。

状态定义：f[c] 表示把整数 c 拆成若干个完全平方数之和所需的最少个数。转移方程（sq 遍历每个完全平方数）：

f[c] = min(f[c], f[c - sq] + 1)        c 从 sq 到 n，**正序**

初值 f[0] = 0（凑出 0 一个数都不用），其余取一个不可能达到的大数当无穷。

容量正序遍历是完全背包的标志，也是这题最该讲透的一点：扫到 f[c] 时，f[c - sq] 有可能已经在本轮被同一个 sq 更新过，于是「再用一个 sq」这件事被自然允许，同一个平方数可以取任意多次。若把容量改成倒序，f[c - sq] 一定还是上一轮的旧值，每个平方数就只能用一次，求出来是 01 背包的答案（n = 12 时凑不出来，f[12] 会停在哨兵上，见「坑在哪」第 3 条）。

另一种同样正确的思路是把它看成无权图上的最短路：从 n 出发，每次减去一个平方数，求到 0 的最少步数，用广度优先搜索逐层扩展。两者的层数与背包的「个数」一一对应。

数据规模与复杂度¶

1 <= n <= 1e4。平方数的个数是 sqrt(n) <= 100，每个平方数扫一遍容量最多 1e4 格，时间 O(n * sqrt(n)) = 1e4 * 100 = 1e6 次内层迭代，本机实测 n = 1e4 约 0.05 秒；判题机比本机慢数倍，仍留有充足余量。空间 O(n)，一个长度 n+1 的整数列表。

这题不需要无解出口：拉格朗日四平方和定理保证任何正整数都能写成至多 4 个完全平方数之和，而且面值 1 本身就是完全平方数，逐个 1 相加总能凑出任何 n。所以答案必然存在且不超过 4。

坑在哪¶

「无穷」取 n + 1 而不是 Python 的 float('inf')。全用面值 1 至多需要 n 个，任何真实答案都不会超过 n，所以 n + 1 一定达不到，足够当哨兵；同时保持整数运算，比浮点比较快。
f[0] = 0 是递推的起点。改成 n + 1 会让所有格子都停在无穷，返回垃圾值。
内层容量必须正序。倒序会把完全背包退化成 01 背包，每个平方数只许用一次。 n = 12 时可用的平方数只有 1、4、9，任何子集之和都凑不出 12 （1+4+9 = 14、4+9 = 13、1+9 = 10），f[12] 会一直停在哨兵值 13 上，函数返回 13 这个垃圾数——而正确答案是 4 + 4 + 4 = 3。
while 的条件是 k * k <= n 而不是 k <= n。写成后者会枚举出大于 n 的平方数，那些 sq 让内层 range 为空，纯属浪费，n = 1e4 时白转 9900 圈。
不要试图用「贪心地每次减去最大的平方数」。n = 12 时贪心会取 9 + 1 + 1 + 1 = 4 个，而最优是 4 + 4 + 4 = 3 个。这类「凑数取最少」的问题在一般面值下贪心不成立，必须 DP。

样例复核¶

n = 12。物品是 1、4、9。

只用 1 时 f[12] = 12；
加入 4 后正序扫描：f[4] = 1, f[8] = f[4] + 1 = 2, f[12] = f[8] + 1 = 3
（这三次更新落在同一轮内层循环里，正是正序遍历允许重复取用的体现）；
加入 9 后 f[12] 的候选是 f[3] + 1 = 3 + 1 = 4，不优于 3。

返回 3，与期望输出 12 = 4 + 4 + 4 一致。

参考实现¶

solutions/leetcode/LC279/sol.py
from typing import List, Optional


class Solution:
    def numSquares(self, n: int) -> int:
        # f[c] = 把 c 拆成完全平方数之和所需的最少个数。
        # f[0] = 0 是递推起点（凑 0 一个都不用）；其余取 n + 1 当「无穷」——
        # 全用 1 至多要 n 个，任何真实答案都不会到 n + 1，用整数比浮点无穷快
        f = [0] + [n + 1] * n
        k = 1
        # 条件是 k * k <= n：大于 n 的平方数一个也放不进去，枚举它们纯属空转
        while k * k <= n:
            sq = k * k
            # 完全背包的标志是容量**正序**：扫到 f[c] 时 f[c-sq] 可能已在本轮
            # 被同一个 sq 更新过，于是同一个平方数被允许重复取用。
            # 倒序则 f[c-sq] 必是上一轮旧值，退化成每个平方数只能用一次的 01 背包
            for c in range(sq, n + 1):
                if f[c - sq] + 1 < f[c]:
                    f[c] = f[c - sq] + 1
            k += 1
        # 拉格朗日四平方和定理保证必有解（面值 1 也是平方数），不需要无解出口
        return f[n]

LC279 完全平方数¶