【LeetCode精选TOP面试题】279-完全平方数

LeetCode 原题链接

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

动态规划解法

思路

用 dp[i] 表示组成 i 所需要的最小完全平方数的数量，最坏的情况下 i 全部由 1 组成，此时有 i 个 1，dp[i] = i。

组成 i 的完全平方数数必然落在区间 [1, sqrt(i)] 之间。

如果将 j * j 作为组成 i 的一部分，则另一部分为 i - j * j。

j * j 是一个完全平方数，则此时 dp[i] = dp[i - j * j] + 1。

从所有可能的组合中取最小值作为 dp[i] 的值，则得出状态转移方程：dp[i] = Math.min(dp[i], dp[i - j * j] + 1)。

复杂度

• 时间复杂度：O(n * sqrt(n))。
• 空间复杂度：O(n)。

代码

// dp[i] 为组成i所需要的最小完全平方数的数量
var numSquares = function (n) {
  const dp = new Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    dp[i] = i; // 最坏的情况，由若干个1组成该数字
    // 能组成i的平方数必然小于sqrt(9)，如：能组成9的完全平方数必然小于3。
    for (let j = 1; i - j * j >= 0; j++) {
      // j * j 是一个完全平方数，则组成 j * j 的最少完全平方数的个数为 1（j）
      // 此时（将 i 分为 i - j * j 和 j * j）组成 i 的最小完全平方数数量等于组成 i - j * j 的最小平方数加 1，则：dp[i] = dp[i - j * j] + 1
      // 如果当前组合的完全平方数个数少于当前记录的数量，则更新dp[i]
      dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
    }
  }
  return dp[n];
};

let result = numSquares(999);
console.log(result);