hot100 完全平方数(279)

本题采用完全背包动态规划算法Unbounded Knapsack DP解决整数拆分为最少完全平方数之和的组合寻优问题。其核心本质是将正整数 n 视作背包的容量上限将所有小于等于 n 的完全平方数1, 4, 9, 16, ...视作体积与价值均等于该数值且数量无限的物品。利用一维顺序滚动数组在遍历物品的同时顺序更新容量状态实现了在时间复杂度 O(N sqrt(N)) 和额外空间复杂度 O(N) 条件下的全局最少组合数计算。最终走向是精准输出凑成目标值 n 所需的最少完全平方数个数。一、 问题本质与完全背包拓扑模型拆解1.1 问题物理约束与完全背包模型映射对于给定的正整数 n题目要求将其拆分为若干个完全平方数之和并求出这些完全平方数的最少数量。这一约束在拓扑结构上可以无缝映射为经典算法中的完全背包问题Unbounded Knapsack Problem背包容量Capacity正整数 n即目标湊出的累加总和。物品集合Items所有小于等于 n 的完全平方数cur i * i如 1, 4, 9, 16, 25, ...。物品属性Item Attributes物品的体积Weight/Cost完全平方数的数值大小cur。物品的价值Value/Count每个完全平方数计为 1 个物品单位求数量极小值时代价固定为 1。物品数量限制Supply无限供给。同一个完全平方数可以在累加和中重复使用多次例如 12 4 4 4完全平方数 4 被使用了 3 次。优化目标Optimization Target用无限供给的完全平方数物品恰好装满容量为 n 的背包使得所使用的物品总件数达到极小值。正整数 n (背包容量) : 12 可选择物品 (完全平方数) : [1, 4, 9] (可重复无限选取) 组合方案 A : 1 1 1 ... 1 (12 个 1) - 物品数量 12 组合方案 B : 9 1 1 1 (1个9, 3个1) - 物品数量 4 组合方案 C : 4 4 4 (3个4) - 物品数量 3 -- 全局最优解 (最少数量)1.2 动态规划状态定义与物理语义为了记录凑成各个中间数值所需的最少完全平方数数量我们需要建立一个一维状态数组f状态数组f[j]其中j的取值范围为0到n。物理语义f[j]表示恰好凑成累加和为 j 所需的最少完全平方数个数。1.3 状态初始化与防溢出设计在初始化阶段数组各位置的数值代表着尚未搜索时的逻辑边界基准状态Base Casef[0] 0。物理含义凑成数值 0 需要 0 个完全平方数。这是整个递推逻辑的源头起点。非零状态Initial State对于1到n的任意j将f[j]初始化为一个极大的安全上限。源码中使用Arrays.fill(f, Integer.MAX_VALUE / 2)。为什么不能直接用 Integer.MAX_VALUE在后续的状态转移公式中存在f[j - cur] 1操作。如果f[j - cur]为Integer.MAX_VALUE执行加 1 操作会导致32 位有符号整型溢出Integer Overflow产生极大的负数Integer.MIN_VALUE从而使Math.min()判定失效并返回错误的负数结果。采用Integer.MAX_VALUE / 2即1073741823既能代表不可达的极值又保留了充足的加法安全冗余空间。二、 算法演进脉络与多重解法综合对比在解决“完全平方数最少数量”这一问题时可以从最原始的记忆化搜索逐步演进到线性的完全背包动态规划甚至跨越到数论定理。下表对比了四种典型解法的时空复杂度与实现特征解法名称时间复杂度空间复杂度核心原理物理瓶颈 / 缺点记忆化搜索 (DFS Memo)O(n * sqrt(n))O(n)自顶向下递归拆分 n利用哈希表或数组记录已计算过的中间结果存在递归函数压栈与弹栈的系统开销在 n 较大时容易导致栈溢出完全背包 DP (当前解法)O(n * sqrt(n))O(n)自底向上递推利用一维顺序滚动数组更新背包容量状态属于通用的多项式时间解法但未利用数论物理特性广度优先搜索 (BFS)O(n * sqrt(n))O(n)将数值视为图节点平方数作为边求 0 到 n 的无权图最短路径需要显式维护队列队内可能积压大量重复节点占用堆内存拉格朗日四平方和定理 (Number Theory)O(sqrt(n)) / O(1)O(1)利用数论定理答案只可能是 1, 2, 3, 4结合公式直接判定依赖高阶数论证明推导复杂且无法通用扩展到非平方数找零问题三、 核心逻辑与状态转移公式严密推导3.1 从二维动态规划到一维滚动数组的降维推导在完全背包问题中如果使用标准的二维状态数组定义f[i][j]为使用前 i 个完全平方数即 1^2, 2^2, ..., i^2凑成数值 j 所需的最少个数。对于第i个完全平方数cur i * i每个状态有两个决策分支不选择第 i 个完全平方数直接继承前i-1个物品凑成容量j的结果即f[i - 1][j]。选择至少一个第 i 个完全平方数先消耗cur的容量剩余容量j - cur继续使用前i个物品可重复选取进行凑数并在结果上加 1代表消耗了 1 个物品即f[i][j - cur] 1。二维状态转移方程为f[i][j] Math.min(f[i - 1][j], f[i][j - cur] 1)由于在计算f[i][j]时所需的左侧状态f[i][j - cur]正好属于当前第 i 层当前物品已经更新过的最新状态因此我们可以彻底消除第一个维度i直接将其压缩为一维滚动数组f[j]。一维状态转移方程简化为f[j] Math.min(f[j], f[j - cur] 1)3.2 外层物品与内层容量的循环顺序证明源码中的双重循环结构如下for (int i 1; i * i n; i) { int cur i * i; for (int j cur; j n; j) { f[j] Math.min(f[j], f[j - cur] 1); } }外层循环for (int i 1; i * i n; i)枚举当前可选的完全平方数物品cur i * i。随着i的增加依次引入1, 4, 9, 16, ...等新物品。内层循环for (int j cur; j n; j)方向必须为从小到大顺序遍历顺序遍历的物理含义在遍历容量j时j - cur位置的状态已经在当前循环中被更新过可能已经包含了若干个当前物品cur。当我们在f[j]中使用f[j - cur] 1时实际上允许了同一个物品cur在当前容量下被无限次重复叠加。这正好精准契合完全背包问题的“物品数量无限”约束。对比 0-1 背包在 0-1 背包物品不可重复选取中内层循环必须为逆序遍历从大到小以确保计算f[j]时引用的f[j - cur]仍属于上一轮未放入当前物品的旧状态。四、 算法执行状态机步进推演与图解为了清晰直观地展示动态规划数组的更新过程以下以n 12为例进行全程步进推演。4.1 初始状态数组f长度为13索引为0到12。初始化后f[0] 0f[1 ... 12] INF(代表Integer.MAX_VALUE / 2 1073741823)索引 j : 0 1 2 3 4 5 6 7 8 9 10 11 12 f[j] : 0 INF INF INF INF INF INF INF INF INF INF INF INF4.2 第一轮外层迭代i 1 (物品 cur 1 * 1 1)内层循环j从1推进至12更新方程为f[j] Math.min(f[j], f[j - 1] 1)j 1:f[1] min(INF, f[0] 1) min(INF, 0 1) 1j 2:f[2] min(INF, f[1] 1) min(INF, 1 1) 2j 3:f[3] min(INF, f[2] 1) min(INF, 2 1) 3...j 12:f[12] min(INF, f[11] 1) 12本轮迭代后的数组状态仅用完全平方数1凑数索引 j : 0 1 2 3 4 5 6 7 8 9 10 11 12 f[j] : 0 1 2 3 4 5 6 7 8 9 10 11 124.3 第二轮外层迭代i 2 (物品 cur 2 * 2 4)内层循环j从4推进至12更新方程为f[j] Math.min(f[j], f[j - 4] 1)j 4:f[4] min(4, f[0] 1) min(4, 0 1) 1(新组合4)j 5:f[5] min(5, f[1] 1) min(5, 1 1) 2(新组合4 1)j 6:f[6] min(6, f[2] 1) min(6, 2 1) 3(新组合4 1 1)j 7:f[7] min(7, f[3] 1) min(7, 3 1) 4(新组合4 1 1 1)j 8:f[8] min(8, f[4] 1) min(8, 1 1) 2(新组合4 4)j 9:f[9] min(9, f[5] 1) min(9, 2 1) 3(新组合4 4 1)j 10:f[10] min(10, f[6] 1) min(10, 3 1) 4(新组合4 4 1 1)j 11:f[11] min(11, f[7] 1) min(11, 4 1) 5(新组合4 4 1 1 1)j 12:f[12] min(12, f[8] 1) min(12, 2 1) 3(新组合4 4 4)本轮迭代后的数组状态允许使用完全平方数1, 4索引 j : 0 1 2 3 4 5 6 7 8 9 10 11 12 f[j] : 0 1 2 3 1 2 3 4 2 3 4 5 34.4 第三轮外层迭代i 3 (物品 cur 3 * 3 9)内层循环j从9推进至12更新方程为f[j] Math.min(f[j], f[j - 9] 1)j 9:f[9] min(3, f[0] 1) min(3, 0 1) 1(新组合9)j 10:f[10] min(4, f[1] 1) min(4, 1 1) 2(新组合9 1)j 11:f[11] min(5, f[2] 1) min(5, 2 1) 3(新组合9 1 1)j 12:f[12] min(3, f[3] 1) min(3, 3 1) 3(维持原组合4 4 4代价相同)最终数组状态允许使用完全平方数1, 4, 9索引 j : 0 1 2 3 4 5 6 7 8 9 10 11 12 f[j] : 0 1 2 3 1 2 3 4 2 1 2 3 3最终输出f[12] 3。算法推演完全正确对应组合 4 4 4。五、 源码实现与逐行硬核注释import java.util.Arrays; class Solution { /** * 计算和为 n 的完全平方数的最少数量 * * param n 目标正整数 * return 凑成 n 的最少完全平方数个数 */ public int numSquares(int n) { // 1. 创建动态规划状态数组 ff[j] 表示凑成数值 j 所需的最少完全平方数个数 int[] f new int[n 1]; // 2. 初始化 DP 数组填充为一个安全的极大值Integer.MAX_VALUE / 2 // 作用防范后续状态转移进行 f[j - cur] 1 操作时发生 32 位有符号整型溢出 Arrays.fill(f, Integer.MAX_VALUE / 2); // 3. 设置基准边界凑成数值 0 所需的完全平方数个数为 0 f[0] 0; // 4. 外层循环枚举所有可用的完全平方数物品 cur i * i // 循环条件 i * i n 限制了物品的体积上限杜绝无效遍历 for (int i 1; i * i n; i) { int cur i * i; // 计算当前完全平方数物品的物理数值 // 5. 内层循环完全背包顺序遍历容量 j起点直接从当前物品体积 cur 开始 // 顺序遍历保证了同一个完全平方数 cur 可以被无限次重复选择 for (int j cur; j n; j) { // 核心状态转移方程 // 不选当前物品保持原 f[j] 不变 // 选择当前物品使用当前物品消耗 cur 容量转化寻找容量 j - cur 的最优解并加 1 f[j] Math.min(f[j], f[j - cur] 1); } } // 6. 返回凑成容量 n 的全局最少完全平方数数量 return f[n]; } }六、 复杂度分析与 JVM 性能剖析6.1 时间复杂度O(n sqrt(n))我们可以精准计算双重循环的实际执行指令总次数外层循环次数i从1增加到sqrt(n)外层循环总共执行sqrt(n)次。内层循环次数对于给定的i内层循环j从i * i递增到n内层循环体执行次数为n - i * i 1次。将内层执行次数进行累加求和总执行次数 sum_{i1}^{sqrt(n)} (n - i * i 1) n * sqrt(n) - sum_{i1}^{sqrt(n)} i^2 sqrt(n)利用自然数平方和公式sum_{i1}^{k} i^2 k * (k 1) * (2k 1) / 6代入k sqrt(n)总执行次数 n * sqrt(n) - (sqrt(n) * (sqrt(n) 1) * (2 * sqrt(n) 1)) / 6 sqrt(n) n * sqrt(n) - (2/6) * n * sqrt(n) - O(n) (2/3) * n * sqrt(n) - O(n)结论主导项系数为2/3算法的总时间复杂度在渐进意义上严格为O(n sqrt(n))。对于题目给定的最大数据范围n 10000sqrt(10000) 100最大指令计算步数约为(2/3) * 10000 * 100 6.67 * 10^5次。这一计算量在 современных CPU 上可在1 毫秒ms内迅速完成。6.2 空间复杂度O(n)辅助数组算法开辟了一个长度为n 1的整型一维数组f。内存开销每个int类型元素占用 4 字节总空间消耗为4 * (n 1)字节。当n 10000时仅消耗约为40 KB的物理堆内存。结论额外空间复杂度为O(n)。6.3 JVM 硬件级 CPU Cache 友情度分析一维滚动数组的完全背包实现在 JVM 与 CPU 硬件层面上具备极高的执行效率连续物理内存与 Cache Line 预取在 Java 堆内存中int[] f是一段物理连续的内存块。CPU 硬件预取单元Hardware Prefetcher会在内层循环for (int j cur; j n; j)推进时顺序将f数组的后续数据提前加载至 64 字节Byte的 CPU L1 Data Cache Line 中。这一顺序访问特征使得L1 Data Cache 命中率逼近 100%。分支预测优化Branch Prediction内层循环中的Math.min(f[j], f[j - cur] 1)属于简单的三元比较与条件赋值。HotSpot JVM JIT 编译器能够将其编译为无分支Branchless的 CPU 指令如 x86 架构下的CMOV条件传送指令彻底消除了因分支预测失败Branch Misprediction引发的 CPU 指令流水线停顿。七、 数论定理拓展与拉格朗日四平方和定理虽然完全背包 DP 是一套通用且易于理解的求解范式但在纯数学与数论领域关于“完全平方数之和”存在一个极其著名的数学定理——拉格朗日四平方和定理Lagranges Four-Square Theorem。7.1 定理内容与物理判定拉格朗日四平方和定理表明任何一个正整数都可以表示为至多四个整数的平方和。也就是说对于任意给定的 n本题的最终答案只可能是 1, 2, 3 或 4 中的一个通过进一步结合勒让德三平方和定理Legendres Three-Square Theorem我们可以直接获得判定答案的数学公式答案为 1当且仅当 n 本身就是一个完全平方数即sqrt(n) * sqrt(n) n。答案为 4当且仅当 n 可以表示为4^a * (8b 7)的形式其中 a, b 为非负整数。我们可以先不断将 n 除以 4如果最终剩下的数模 8 余 7则答案必然是 4。答案为 2当且仅当 n 不满足答案为 1 和 4 的条件且 n 可以拆分为两个完全平方数之和即存在a使得n - a * a是完全平方数。我们可以在O(sqrt(n))时间内枚举a进行验证。答案为 3如果以上条件全不满足则根据排除法答案必然为 3。7.2 数论方法实现代码 (Java)class MathematicalSolution { public int numSquares(int n) { // 1. 判断答案是否为 1n 本身是否是完全平方数 if (isSquare(n)) { return 1; } // 2. 判断答案是否为 4满足 4^a * (8b 7) 格式 int temp n; while (temp % 4 0) { temp / 4; } if (temp % 8 7) { return 4; } // 3. 判断答案是否为 2枚举 a看 n - a*a 是否为完全平方数 for (int i 1; i * i n; i) { if (isSquare(n - i * i)) { return 2; } } // 4. 剩余情况答案必然为 3 return 3; } private boolean isSquare(int n) { int sq (int) Math.sqrt(n); return sq * sq n; } }数论解法复杂度时间复杂度下降至O(sqrt(n))空间复杂度下降至O(1)。范式对比数论解法虽然性能极佳但属于特定问题下的专效数学解法泛化能力较弱而完全背包 DP 解法可以无缝扩展到任何找零问题如 LeetCode 322. 零钱兑换、任意集合组合数问题等属于通用型算法思想。八、 工程实战避坑指南与总结8.1 经典避坑指南数值溢出隐患Integer Overflow千万不要将f数组初始化为Integer.MAX_VALUE。因为后续存在f[j - cur] 1表达式这会导致 32 位整型下溢变成极大的负数破坏Math.min()的比较结果。建议统一使用Integer.MAX_VALUE / 2或0x3f3f3f3f。内层循环方向错误完全背包问题中内层循环必须顺序遍历j从cur递增到n如果是 0-1 背包问题内层循环必须逆序遍历j从n递减到cur。混淆循环方向会导致物品使用次数限制混乱。内外层循环颠倒的影响在本题求物品最少数量中内外层循环顺序可以互换不影响最终数值结果。但在求组合数/排列数的背包问题中如 LeetCode 377. 组合总和 Ⅳ外层循环枚举容量、内层枚举物品代表求排列数外层枚举物品、内层枚举容量代表求组合数。8.2 核心要点终极复盘物理本质将数值 n 抽象为完全背包容量完全平方数抽象为无限制供给的物品。状态设计一维滚动数组f[j]代表凑成数值j的最少平方数个数。状态转移f[j] Math.min(f[j], f[j - cur] 1)借由顺序遍历实现物品无限次重复选取。复杂度表现时间复杂度 O(n sqrt(n))空间复杂度 O(n)属于稳定且通用性强的极效算法。