LeetCode题解：279. 完全平方数，动态规划，JavaScript，详细注释

[chencl1986]

原题链接：279. 完全平方数

解题思路：

1. 本题类似于322. 零钱兑换，如果你对322. 零钱兑换不熟悉，可以先看题解。二者的区别是硬币种类不固定，在本题中，对于当前金额i，硬币种类为小于i的完全平方数。
2. 该题递推的是从1开始，使用小于i完全平方数，计算能够凑到i的最小数量，由此不断累加到n的过程。
3. 创建一个长度为n + 1的dp数组，用索引就表示从0到n的数字。
4. 对于当前数字i，我们可以用for (let j = 1; j * j <= i; j++) {}，计算出小于i的完全平方数。
5. i是由i - j * j用1个j * j凑过来，同时要保证它是所有结果中最小的一个，因此状态转移返程为：dp[i] = Math.min(dp[i], dp[i - j * j] + 1);。

/**
 * @param {number} n
 * @return {number}
 */
var numSquares = function (n) {
  // 需要计算到n，因此需要从0开始递推到n
  // 由于要计算的是最小值，因此初始化为Infinity，避免计算错误
  let dp = new Array(n + 1).fill(Infinity);
  dp[0] = 0; // 0对应的可组合数字为0

  // 从1开始才会有组合个数，一直递推到n
  for (let i = 1; i < dp.length; i++) {
    // 每次计算可用的完全平方数
    // 判断可用的方法是j*j不超过当前数量i
    for (let j = 1; j * j <= i; j++) {
      // 因为j * j <= i，所以i - j * j不可能小于0，无需判断
      dp[i] = Math.min(
        dp[i], // 当前已储存了之前完全平方数的组合数量
        // 当前的完全平方数数量，可由i - j * j加一个j * j而来
        // 因此等于dp[i - j * j]的数量加1个j * j
        dp[i - j * j] + 1,
      );
    }
  }

  // 递推到n时，就计算出了所有可能的数量
  return dp[n];
};