279. 完全平方数 - 力扣LeetCode中等给你一个整数n返回和为n的完全平方数的最少数量。完全平方数是一个整数其值等于另一个整数的平方换句话说其值等于一个整数自乘的积。例如1、4、9和16都是完全平方数而3和11不是。示例 1输入n 12 输出3 解释12 4 4 4示例 2输入n 13 输出2 解释13 4 9提示1 n 104 核心笔记完全平方数 (Perfect Squares - Unbounded Knapsack)1. 核心思想 (一句话总结)“找零钱问题把1, 4, 9, 16...看作不同面额的硬币目标是凑出总额n问最少需要几枚硬币”模型完全背包Unbounded Knapsack。区别0/1 背包选了就得跳到i-1而这里选了当前平方数 还可以继续留在i再选一次例如 。Static 技巧题目会多次调用numSquares利用static缓存计算过的结果比如dfs(..., 12)在下一个测试用例里可以直接用。2. 算法流程 (DFS Static Memo)预处理 (Static Init)创建static int[][] memo。利用static {}块初始化为 -1。这在类加载时只执行一次。入口 (Entry)物品范围是 到 。所以从(int)Math.sqrt(n)开始递归。递归 (Recursion)Base Casei 0。如果没有物品可选了只有当剩余金额j 0时算成功0步否则失败返回无穷大。不选dfs(i - 1, j)。觉得 不合适去看小一点的平方数。选dfs(i, j - i * i) 1。注意这里第一个参数是i而不是i-1。表示“我选了一个 但我还可以继续选它”。决策取两者最小值。 代码回忆清单// 题目LC 279. Perfect Squares class Solution { // 1. 静态缓存所有测试用例共享避免重复计算 // 100^2 10000所以 i 最大 100j 最大 10000 private static final int[][] memo new int[101][10001]; static { for (int[] row : memo) { Arrays.fill(row, -1); } } private static int dfs(int i, int j) { // 2. Base Case: 物品遍历完了 if (i 0) { // 如果刚好凑整返回 0 步否则返回 MAX_VALUE 表示此路不通 return j 0 ? 0 : Integer.MAX_VALUE; } // 3. 查表 if (memo[i][j] ! -1) { return memo[i][j]; } // 4. 剪枝如果当前平方数比剩余容量还大只能不选 if (j i * i) { return memo[i][j] dfs(i - 1, j); } // 5. 核心转移完全背包 // 选 i 的话状态依然留在 i (允许重复选) - dfs(i, ...) // 不选 i 的话状态去往 i-1 - dfs(i-1, ...) return memo[i][j] Math.min( dfs(i - 1, j), dfs(i, j - i * i) 1 ); } public int numSquares(int n) { return dfs((int) Math.sqrt(n), n); } }⚡ 快速复习 CheckList (易错点)[ ]为什么是dfs(i, ...)而不是dfs(i-1, ...)这是完全背包的标志。如果选了i后变成dfs(i-1)那就变成了 0/1 背包每个平方数只能用一次这不符合题意比如 12 可以由三个 4 组成。[ ]Static 的副作用在 LeetCode 这种 OJ 环境是神技。在实际工程或多线程环境下是不安全的脏数据、并发竞争。但在刷题时它能帮你打败 99% 的用户。[ ]Integer.MAX_VALUE会导致溢出吗逻辑上min(..., MAX_VALUE 1)会溢出变成负数。但这道题不用担心因为1也是平方数。也就是说任何整数 n 都可以由 n 个 1 组成。所以dfs永远有一条保底路径全选 1绝对不会返回MAX_VALUEmin函数总是能选到那个正常的值。️ 数字演练n 12物品列表平方数[1, 4, 9] (即 $1^2, 2^2, 3^2$)启动dfs(3, 12):Path A (不选 9):dfs(2, 12)。Path B (选 9):1 dfs(3, 3)。dfs(3, 3): 9 3装不下强制不选 9 -dfs(2, 3)。dfs(2, 3): 4 3装不下强制不选 4 -dfs(1, 3)。dfs(1, 3): 选三个 1。返回 3。Path B 总代价: 。也就是 。回看 Path Adfs(2, 12)(只考虑 4 和 1):尝试选 4:1 dfs(2, 8)。再选 4:1 1 dfs(2, 4)。再选 4:1 1 1 dfs(2, 0)。dfs(2, 0): 凑齐了返回 0。Path A 总代价: 。也就是 。最终比较:min(Path A, Path B)-min(3, 4)。返回3。 核心笔记完全平方数 (Static DP - Iterative)1. 核心思想 (一句话总结)“一次算好终身受用把所有 1 到 10000 的答案提前算好填在表格里。填表时每个完全平方数都可以被‘无限次’使用这正是完全背包的特征。”模型完全背包。物品是 容量是 $N$。状态f[i][j]表示只使用前i个完全平方数凑出j所需的最少数量。打表 (Pre-computation)利用static代码块将 $N10000$ 范围内所有的最优解预先算好。2. 算法流程 (Static Execution)类加载 (Class Load)执行static块。初始化第 0 行除了f[0][0]0其余全设为MAX_VALUE没有物品凑不出正整数。填表 (Tabulation)外层物品i从 1 遍历到 100 (因为 $100^2 10000$)。内层容量j从 0 到 10000。转移不选f[i-1][j]。选f[i][j - i*i] 1。注意这里是f[i]表示选了还能再选。调用 (Call)numSquares(n)直接返回f[(int)sqrt(n)][n]。其实返回f[100][n]也是对的因为更大的平方数反正也用不上但写sqrt(n)逻辑上更严谨。 代码回忆清单// 题目LC 279. Perfect Squares class Solution { private static final int N 10000; // f[i][j]: 使用前 i 个平方数凑出 j 的最小个数 private static final int[][] f new int[101][N 1]; // 1. 静态代码块类加载时执行一次后续所有 Test Case 共享 static { // 2. 初始化没有物品(Row 0)无法凑出任何数(除了0) Arrays.fill(f[0], Integer.MAX_VALUE); f[0][0] 0; // 3. 外层循环物品 (1, 2, ... 100) for (int i 1; i * i N; i) { int weight i * i; // 物品重量 (平方数值) // 4. 内层循环容量 (0 ... 10000) for (int j 0; j N; j) { if (j weight) { // 装不下只能继承上一行 f[i][j] f[i - 1][j]; } else { // 装得下完全背包核心 // min(不选, 选了之后状态还在当前行 i) f[i][j] Math.min(f[i - 1][j], f[i][j - weight] 1); } } } } public int numSquares(int n) { // 5. O(1) 查表返回 // 只用前 sqrt(n) 个物品凑出 n 即可 return f[(int) Math.sqrt(n)][n]; } }⚡ 快速复习 CheckList (易错点)[ ]状态压缩这是二维写法。完全背包可以优化成一维数组f[j] min(f[j], f[j - weight] 1)。一维写法必须正序遍历j(从weight到N)这与 0/1 背包的一维倒序相反。[ ]为什么f[i][j - i*i]用的是i如果用i-1表示选了这个平方数后这辈子不能再选它了0/1 背包。用i表示选了它之后我们还停留在第i行下次还能继续选它比如 。[ ]f[0]行初始化的坑必须设为MAX_VALUE。如果默认是 0计算min时会错误地认为“不用任何平方数凑出 5 需要 0 步”。️ 数字演练假设 N5(只看前几列)物品Row 0 (Init):[0, INF, INF, INF, INF, INF]Row 1 (Item 1):j1:min(INF, f[1][0]1) 1。j2:min(INF, f[1][1]1) 2。...f[1]行全填满[0, 1, 2, 3, 4, 5](全用 1 组成)。Row 2 (Item 4):j0..3: 4 比 j 大只能不选 - 继承上一行[0, 1, 2, 3].j4:min(f[1][4]4, f[2][0]11) 1。 (直接用一个4)j5:min(f[1][5]5, f[2][1]12) 2。 (4 1)Result:f[2][5] 2。