279.完全平方数

链接：279.完全平方数
难度：Medium
标签：广度优先搜索、数学、动态规划
简介：给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。

题解 1 - typescript

• 编辑时间：2021-06-11
• 执行用时：292ms
• 内存消耗：41.8MB
• 编程语言：typescript
• 解法介绍：背包问题。

function numSquares(n: number): number {
  let MAX = 1;
  const dp = new Array(n + 1).fill(Infinity);
  dp[0] = 0;
  dp[1] = 1;
  for (let i = 2; i <= n; i++) {
    while (MAX ** 2 <= i) MAX++;
    for (let j = MAX - 1; j >= 1; j--) {
      const num = j ** 2;
      if (num > i) continue;
      const count = ~~(i / num);
      dp[i] = Math.min(dp[i], dp[i - num * count] + count);
    }
  }
  return dp[n];
}

题解 2 - typescript

• 编辑时间：2021-07-22
• 执行用时：200ms
• 内存消耗：41.9MB
• 编程语言：typescript
• 解法介绍：背包问题。

function numSquares(n: number): number {
  const dp = new Array(n + 1).fill(Infinity);
  dp[0] = 0;
  dp[1] = 1;
  for (let i = 2; i < n + 1; i++) {
    for (let j = 1; j ** 2 <= i; j++) {
      dp[i] = Math.min(dp[i - j ** 2] + 1, dp[i]);
    }
  }
  return dp[n];
}