企业官网建设流程全解析

👋 欢迎阅读

🎯 欢迎来到「完全平方数」题解之旅！本文将带你从“用最少的平方数拼出给定整数”这一数学问题出发，深入理解完全背包求最小值的 DP 模型，并掌握如何将隐式物品（平方数）动态生成融入背包框架。

在开始之前，建议你先：

• 了解题目背景：这是 LeetCode 279 题，给定整数 nn，求最少需要多少个完全平方数（1, 4, 9, 16, ...）相加得到 nn。本质上，我们可以把每个平方数看作一种无限量供应的物品，体积为该平方数的值，价值为 1（即硬币个数），目标是用最少的物品凑满容量为 nn 的背包。

• 明确学习目标：掌握如何将“最少平方数数量”转化为完全背包求最小值，理解物品列表的动态生成（只需用到 1212 到 ⌊n⌋2⌊n​⌋2），并熟练使用INF 初始化不可达状态以及dp[0] = 0的起点设定。

• 准备好环境：建议在本地 IDE 或 LeetCode 在线编辑器中打开代码，边看边运行，亲手验证示例（如 n=12n=12 输出 3，对应 4+4+44+4+4）。

本文将从问题转化、状态定义、转移方程、初始化、填表顺序到代码实现，层层递进。即使你对完全背包还不熟悉，我们也会从“零钱兑换”的类比出发，让你轻松抓住核心思想——平方数即硬币的建模技巧，以及正序内层循环在完全背包中的关键作用。现在，让我们一起用最少的平方数拼出目标，解开完全平方数的 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到row（row = ⌊√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] = INF（j > 0）：没有平方数可用时，无法凑出任何正数，标记为不可达。
  代码中通过循环for (int j=1; j<=n; ++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，但题目保证n>=1，所以结果总是有限的。

三、代码

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 所需的最少个数 vector<vector<int>> dp(row + 1, vector<int>(col + 1)); // 2. 初始化： // dp[0][0] = 0（不使用任何平方数，凑成0需要0个） // dp[0][j] = INF（j>0时，不使用任何平方数无法凑成，设为不可达） for (int j = 1; j <= col; j++) { dp[0][j] = INF; } // dp[0][0] 默认为0（vector初始化已为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]仍为上一轮状态，则每个平方数最多被选一次，无法实现重复选取，结果错误（例如n=12时只能选4+4+4需要三次，逆序会漏算）。

与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（不可达） vector<int> 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^9），sqrt(n)也很大，DP 会超时，你能想到哪些优化思路（？

📚延伸挑战

• 将题目改为用完全平方数凑成 n 的组合数（不同顺序视为同一种），类比零钱兑换 II，状态转移和初始化应如何调整？

• 如果每个完全平方数最多只能用一次（即 01 背包），代码只需改动哪一处？动手改一改，并验证n=12时结果会变成多少。

• 考虑最少数量的同时，如果还要输出具体的平方数组合（如12=4+4+4），你如何在 DP 过程中记录路径并回溯？

如果你觉得本文对你有所帮助，欢迎：

👍 点赞 / 收藏
👤 关注作者，获取更多题解
💬 留言交流你的疑问或优化思路

祝你在DP 的道路上越走越稳，早日攻克每一道难题！下次见 🚀✨