279. 完全平方数
给你一个整数 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 <= 10^4
思路分析
本题要求将整数 n 分解为若干个完全平方数的和，并返回所需完全平方数的最少数量。这是一个经典的动态规划问题，可以类比为完全背包问题。
- 物品：完全平方数（如1，4，9，16...），每个物品可以无限次使用
- 背包容量：目标整数n。
- 目标：恰好装满背包所需的最少物品数量。
动态规划步骤
- 状态定义：定义 dp[i] 表示和为 i 时所需的最少完全平方数数量。
- 初始化：
- dp[0] = 0（和为0时不需要任何平方数）。
- 其他位置初始化为一个较大的值（如 n + 1），因为最多由 n 个1组成。（因为要求最小值，所以初始化为一个大于可能最大值的数，比如n+1，因为最多就是n个1相加）。
- 状态转移：
- 对于每个 i（从1到n），遍历所有可能的平方数 j * j（其中 j * j <= i）。
- 状态转移方程：dp[i] = min(dp[i], dp[i - j * j] + 1)。
- 最终结果：dp[n]即为答案。
优化
- 内层循环只需遍历 j 从 1 到 sqrt(i) ，避免无效计算。
- 时间复杂度：O(n√n)，空间复杂度：O(n)。
完整代码
class Solution { public int numSquares(int n) { // 创建dp数组，dp[i]表示和为i所需的最少完全平方数的个数 int[] dp = new int[n + 1]; // 初始化dp数组，初始值设为n+1（一个大于最大可能值的数） for(int i = 0; i <= n; i++){ dp[i] = n + 1; // 初始化为最大值 } dp[0] = 0; // 动态规划填表 for(int i = 1; i <= n; i++){ // 遍历所有平方数 j*j（j从1开始，直到 j*j<=i） for(int j = 1; j * j <= i; j++){ dp[i] = Math.min(dp[i], dp[i - j * j] + 1); } } // 返回结果 return dp[n]; }}代码解析
初始化：
dp[0] = 0表示和为 0 时不需要任何平方数。其他
dp[i]初始化为n + 1（因为最多需要n个 1，所以n + 1是一个安全的上界）。
动态规划填表：
外层循环遍历
i从 1 到n，计算每个i所需的最少平方数。内层循环遍历所有可能的平方数
j * j（j从 1 开始，直到j * j > i停止）。对于每个
j，尝试使用平方数j * j，更新dp[i]为dp[i - j * j] + 1的最小值。
返回结果：
最终
dp[n]存储了和为n所需的最少完全平方数数量。
示例验证
示例 1（n = 12）：
计算过程：
dp[12] = min(dp[11]+1, dp[8]+1, dp[3]+1)→ 最终得到 3（4+4+4）。
示例 2（n = 13）：
计算过程：
dp[13] = min(dp[12]+1, dp[9]+1, dp[4]+1)→ 最终得到 2（4+9）。