完全平方数

题面

给你一个整数 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

分析

• dp[i] 表示和为数字 i 的完全平 方数的最少数量

• 首先，所有完全平方数的 dp[i] 等于 1，即由其自身组成

• 在遍历时，如果当前数本身已经是完全平方数，则直接跳过

• 内层循环中，遍历所有可能的完全平方数 j*j，计算 i = (i - j*j) + j*j，因此 dp[i] 的最小值 = dp[i - j*j] + 1（j*j 是 1 个完全平方数）

• 当内层遍历至得到 dp[i]==2 时，已经是最优解，可以直接终止内层循环

• 代码实现

  class Solution {
  public:
      int numSquares(int n) {
          vector<int> dp = vector(n + 1, n + 1);
          for (int i = 1; i * i <= n; i++) {
              dp[i * i] = 1;
          }
          for (int i = 1; i <= n; i++) {
              if (dp[i] == 1)
                  continue;
              for (int j = 1; j * j <= i; j++) {
                  dp[i] = min(dp[i], dp[i - j * j] + 1);
                  if (dp[i] == 2)
                      break;
              }
          }
          return dp[n];
      }
  };

• 实际上，这是一个完全背包问题，即背包容量为 n，物品则是所有小于等于 n 的完全平方数，物品的重量是完全平方数的数值本身，物品的价值都是 1，而优化目标是恰好装满容量时，所需物品的最小价值和

  完全背包概念	完全平方数问题中的对应项
  背包容量	目标整数 n
  物品	所有小于等于 n 的完全平方数（1,4,9,16...）
  物品 “重量”	完全平方数的数值本身（如 4 的 “重量” 是 4）
  物品 “价值”	每个完全平方数的 “价值” 都是 1（选一个算 1 个）
  优化目标	恰好装满容量 n 时，所需物品的最小价值和

• 代码实现

  int numSquares(int n) {
      // 1. 初始化dp数组：dp[j]表示装满容量j的背包所需的最小物品数
      vector<int> dp(n + 1, INT_MAX);
      dp[0] = 0;  // 装满容量0的背包，需要0个物品（完全背包的标准初始值）
      
      // 2. 遍历物品（所有完全平方数）
      for (int i = 1; i * i <= n; i++) {
          int square = i * i;  // 当前物品（完全平方数）
          // 3. 遍历背包容量（正序遍历，因为物品可重复选）
          for (int j = square; j <= n; j++) {
              if (dp[j - square] != INT_MAX) {
                  dp[j] = min(dp[j], dp[j - square] + 1);
              }
          }
      }
      return dp[n];
  }

• 空间优化：

题解

• 把 1, 4, 9, 16, … 这些完全平方数视作物品体积，物品价值都是 1。由于每个数（物品）选的次数没有限制，所以本题是一道标准的完全背包问题

• 定义 dfs(i, j) 表示从前 i 个完全平方数中选一些数（可以重复选），满足元素和恰好等于 j，最少要选的数字个数

• 考虑第 i 个完全平方数 i² 选或不选：

  • 不选：问题变成从前 i-1 个完全平方数中选一些数（可以重复选），满足元素和恰好等于 j，最少要选的数字个数，即 dfs(i, j) = dfs(i-1, j)

  • 选：前提是 j ≥ i²。问题变成从前 i 个完全平方数中选一些数（可以重复选），满足元素和恰好等于 j - i²，最少要选的数字个数，即 dfs(i, j) = dfs(i, j - i²) + 1。注意这里是 i 而不是 i-1，因为我们可以继续选第 i 个完全平方数

• 这两种情况取最小值，就得到了 dfs(i, j)，即

  $$dfs(i, j) = \begin{cases} dfs(i-1, j), & j < i^2 \\ \min\bigl(dfs(i-1, j),\ dfs(i, j - i^2) + 1\bigr), & j \ge i^2 \end{cases}$$

• 递归边界：dfs(0, 0) = 0，因为没有数可以选了，且要得到的数等于 0，那么答案为 0。如果 j > 0，那么 dfs(0, j) = ∞，这里用 ∞ 表示不合法的状态，从而保证上式中的 min 取到合法的状态。注意本题是一定有解的，因为 1 是完全平方数

• 递归入口：由于 i² ≤ n，所以 i ≤ ⌊√n⌋，所以递归入口为 dfs(⌊√n⌋, n)，也就是答案

• 在计算 n = 7 的时候，如果选了 4，会递归到 n = 3 的情况。这个例子意味着多个测试数据之间可以共享记忆化搜索的结果。因此，把记忆化搜索的 memo 数组声明为全局变量，这样可以在多个测试数据之间共享，从而减少计算量

• 进一步转换为递推之后，就是动态规划写法

  const int N = 10000;
  int f[101][N + 1];
  
  auto init = [] {
      ranges::fill(f[0], INT_MAX);
      f[0][0] = 0;
      for (int i = 1; i * i <= N; i++) {
          for (int j = 0; j <= N; j++) {
              if (j < i * i) {
                  f[i][j] = f[i - 1][j]; // 只能不选
              } else {
                  f[i][j] = min(f[i - 1][j], f[i][j - i * i] + 1); // 不选 vs 选
              }
          }
      }
      return 0;
  }();
  
  class Solution {
  public:
      int numSquares(int n) {
          return f[(int) sqrt(n)][n]; // 也可以写 f[100][n]
      }
  };