[279] 完全平方数

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

示例 1:

输入：n = 12

输出：3

解释：12 = 4 + 4 + 4.

示例 2:

输入：n = 13

输出：2

解释：13 = 4 + 9.

我们注意到，一个数 n 能被完全平方和数相加得出，那么 n 的最大完全平方和的因数一定为 sqrt(n) 后向下取整。

即当前数字 i 的最小平方和组成个数为：i 减去一个比该数小的平方数 j^2 后的数所需要的最小平方和组成个数+1（这个 1 指代的就是 j) 的所有情况的最小值

因此，这就转化为了一个背包容量 n，因数物品种类有限 sqrt(n) 向下取整，数量无限的完全背包问题。

当 n 为 0 时，显然组成其的完全平方数的最小数量为 0 个。

解法显而易见。

function numSquares(n: number): number {
  const maxFactor = Math.floor(Math.pow(n, 0.5));
  const maxNum = Number.MAX_SAFE_INTEGER;

  const dp = Array(maxFactor + 1)
    .fill(0)
    .map(x => Array(n + 1).fill(maxNum));

  for (let i = 1; i <= maxFactor; i++) {
    dp[i][0] = 0;
    const square = Math.pow(i, 2);

    for (let j = 1; j <= n; j++) {
      dp[i][j] = dp[i - 1][j];
      if (j >= square) {
        dp[i][j] = Math.min(dp[i][j], dp[i][j - square] + 1);
      }
    }
  }
}

之后我们发现解法中不需要记录 dp[i]，因此省略该复杂度。

function numSquares(n: number): number {
  const maxFactor = Math.floor(Math.pow(n, 0.5));
  const maxNum = Number.MAX_SAFE_INTEGER;

  const dp = Array(n + 1).fill(maxNum);
  dp[0] = 0;

  for (let i = 1; i <= maxFactor; i++) {
    const square = Math.pow(i, 2);
    for (let j = 1; j <= n; j++) {
      if (j >= square) {
        dp[j] = Math.min(dp[j], dp[j - square] + 1);
      }
    }
  }

  return dp[n];
}

另外，如果对性能精益求精的话，我们还可以做一些数学优化 -- 四平方和定理。

四平方和定理：任何正整数都能表示为 4 个整数的平方和。

因此我们可以提前做一些优化。

  if (n <= 0) return 0;
  // 四平方和定理提高算法效率，不知道该定理可以不加这两行
  while (n % 4 === 0) n /= 4;
  if (n % 8 === 7) return 4;