欢迎阅读 欢迎来到「完全平方数」题解之旅本文将带你从“用最少的平方数拼出给定整数”这一数学问题出发深入理解完全背包求最小值的 DP 模型并掌握如何将隐式物品平方数动态生成融入背包框架。在开始之前建议你先了解题目背景这是 LeetCode 279 题给定整数 nn求最少需要多少个完全平方数1, 4, 9, 16, ...相加得到 nn。本质上我们可以把每个平方数看作一种无限量供应的物品体积为该平方数的值价值为 1即硬币个数目标是用最少的物品凑满容量为 nn 的背包。明确学习目标掌握如何将“最少平方数数量”转化为完全背包求最小值理解物品列表的动态生成只需用到 1212 到 ⌊n⌋2⌊n​⌋2并熟练使用INF 初始化不可达状态以及dp[0] 0的起点设定。准备好环境建议在本地 IDE 或 LeetCode 在线编辑器中打开代码边看边运行亲手验证示例如 n12n12 输出 3对应 444444。本文将从问题转化、状态定义、转移方程、初始化、填表顺序到代码实现层层递进。即使你对完全背包还不熟悉我们也会从“零钱兑换”的类比出发让你轻松抓住核心思想——平方数即硬币的建模技巧以及正序内层循环在完全背包中的关键作用。现在让我们一起用最少的平方数拼出目标解开完全平方数的 DP 密码吧 ✨一、题目279. 完全平方数 - 力扣LeetCode二、做题思路问题转化前置分析本题要求用最少的完全平方数可重复使用之和凑成整数n。将问题转化为完全背包求最小值背包容量 n物品所有完全平方数1^2, 2^2, ..., (√n)^2每种数量无限物品体积 平方数的值物品价值 1每个平方数贡献 1 个数量目标恰好装满容量n最小化总价值平方数个数不可达状态用INF大数标记。1. 状态表示核心基础定义dp[i][j]表示使用前i个平方数即1^2, 2^2, ..., i^2凑成整数j所需的最少个数。i范围0到rowrow ⌊√n⌋表示平方数种类数j范围0到n。2. 状态转移方程关键难点对于第i个平方数值为square i*i有两种决策不选个数为dp[i-1][j]继承上一行的结果。选至少一枚前提是j square个数为dp[i][j - square] 1。注意此处使用的是dp[i][...]而非dp[i-1][...]因为完全背包允许重复选取当前平方数dp[i][j - square]可能已经包含了当前平方数的多次使用这体现了无限取用的特性。取两者最小值dp[i][j] min(dp[i-1][j], (j square ? dp[i][j - square] 1 : INF))。3. 初始化边界防护dp[0][0] 0不使用任何平方数凑出整数0需要0个可行。dp[0][j] INFj 0没有平方数可用时无法凑出任何正数标记为不可达。代码中通过循环for (int j1; jn; j) dp[0][j] INF;实现dp[0][0]保持默认0。其余dp[i][j]初始化为0但会在递推中被覆盖。4. 填表顺序递推方向dp[i][j]依赖上一行dp[i-1][j]和当前行左侧dp[i][j - square]因此必须按行从上到下i从 1 到row列从左到右j从 1 到n遍历。5. 返回值目标映射最终返回dp[row][n]即使用所有平方数凑成整数n的最少个数。若不可达理论上不会因为1是平方数总能凑出则返回INF但题目保证n1所以结果总是有限的。三、代码class Solution { public: int numSquares(int n) { // 将问题转化为完全背包 // 物品所有平方数 1^2, 2^2, ..., (sqrt(n))^2每种数量无限 // 背包容量n // 目标用最少的物品数恰好装满背包 int row sqrt(n); // 平方数的个数即物品种类数 int col n; // 背包容量 const int INF 0x3f3f3f3f; // 1. 创建dp表 // dp[i][j] 表示使用前 i 个平方数1^2 ~ i^2凑成整数 j 所需的最少个数 vectorvectorint dp(row 1, vectorint(col 1)); // 2. 初始化 // dp[0][0] 0不使用任何平方数凑成0需要0个 // dp[0][j] INFj0时不使用任何平方数无法凑成设为不可达 for (int j 1; j col; j) { dp[0][j] INF; } // dp[0][0] 默认为0vector初始化已为0 // 3. 填表顺序外层遍历平方数种类i从1到row内层遍历容量j从1到col // 因为完全背包允许重复使用同一种平方数所以内层容量正序遍历 // 使得 dp[i][j - i*i] 已经考虑过当前平方数的多次使用。 for (int i 1; i row; i) { int square i * i; // 当前平方数的值 for (int j 1; j col; j) { // 4. 状态转移方程完全背包二维形式 // 不选当前平方数dp[i][j] dp[i-1][j] dp[i][j] dp[i - 1][j]; // 选当前平方数至少一次前提是 j square // 此时 dp[i][j - square] 1 表示用当前平方数补足剩余容量 // 取最小值更新。 if (j square) { dp[i][j] min(dp[i][j], dp[i][j - square] 1); } } } // 5. 返回值dp[row][col] 即为用所有平方数凑成 n 的最少个数 return dp[row][col]; } };四、流程图五、优化状态转移方程对于当前平方数square i*i第i种决策为选或不选但由于可重复选一维转移为dp[j] min(dp[j], dp[j - square] 1)当j square时。dp[j]左侧等号右边为上一轮不选当前平方数的值即继承旧状态。dp[j - square]为本轮已更新的值表示已经选过至少一枚当前平方数后继续累加的数量这允许无限次使用同一平方数。填表顺序外层循环遍历每种平方数i从 1 到row内层循环必须正序遍历整数j从 1 到n。为什么完全背包要正序从左到右因为完全背包允许无限次选取当前平方数dp[j]需要利用同一平方数已更新过的较小整数状态dp[j - square]即表示“已经选过一枚当前平方数后继续选”的累计数量。当j从小到大遍历时dp[j - square]已经在本轮被更新过因为j - square j先被处理所以它包含了当前平方数的多次使用信息从而允许无限取用。若采用逆序如01背包dp[j - square]仍为上一轮状态则每个平方数最多被选一次无法实现重复选取结果错误例如n12时只能选444需要三次逆序会漏算。与01背包逆序的对比01背包中每个物品只能选一次必须保证dp[j - square]是上一轮状态因此需要逆序遍历容量避免覆盖。class Solution { public: int numSquares(int n) { int row sqrt(n); // 平方数种类数1^2 ~ row^2 int col n; const int INF 0x3f3f3f3f; // 一维滚动数组 dp[j]表示当前已考虑的平方数种类下凑成金额 j 的最少个数 // 初始时未考虑任何平方数仅 dp[0]0 可达0个其余为 INF不可达 vectorint dp(col 1); for (int j 1; j col; j) { dp[j] INF; } // 外层遍历平方数种类相当于完全背包的物品内层正序遍历容量 // 正序使得 dp[j - i*i] 在本轮已被更新允许同一平方数重复使用完全背包特性 for (int i 1; i row; i) { int square i * i; for (int j 1; j col; j) { if (j square) { // dp[j] 保留旧值不选当前平方数 // 或从 dp[j - square] 1 转移选一个当前平方数复用本轮更新的结果 dp[j] min(dp[j], dp[j - square] 1); } } } return dp[col]; } }; 闭幕 恭喜你完成了「完全平方数」问题的学习为了巩固知识并进一步拓展建议你动手实践在 LeetCode 上提交代码尝试不同的测试用例。深入思考本题将完全平方数视为物品n视为背包容量求最少数量这属于完全背包的恰好装满问题。代码中dp[0][0]0其他dp[0][j]INF为什么这样初始化如果把dp[0][j]也设为0输出会有什么变化物品列表只取到sqrt(n)的平方数为什么不需要考虑更大的平方数如(sqrt(n)1)^2本题直接用数学方法四平方和定理也能求解但 DP 更加通用。你觉得 DP 和定理法各自的优缺点是什么如果n非常大如10^9sqrt(n)也很大DP 会超时你能想到哪些优化思路延伸挑战将题目改为用完全平方数凑成 n 的组合数不同顺序视为同一种类比零钱兑换 II状态转移和初始化应如何调整如果每个完全平方数最多只能用一次即 01 背包代码只需改动哪一处动手改一改并验证n12时结果会变成多少。考虑最少数量的同时如果还要输出具体的平方数组合如12444你如何在 DP 过程中记录路径并回溯如果你觉得本文对你有所帮助欢迎 点赞 / 收藏 关注作者获取更多题解 留言交流你的疑问或优化思路祝你在DP 的道路上越走越稳早日攻克每一道难题下次见 ✨