完全平方数

• 完全平方数
  • 题目详情
  • 解题思路
  • 代码实现

题目详情

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

解题思路

学会了，从暴力法开始往动态规划推

• 暴力法思路：

1. 定义一个函数 numSquares(n)，它返回组成整数 n 所需要的最少的完全平方数的数量。

2. 如果 n 是一个完全平方数，那么直接返回 1。

3. 否则，对于每一个小于 n 的完全平方数 ii，计算 numSquares(n - ii)，并找出这些值中的最小值 min。

4. 返回 min + 1。

• 动规法思路：

1. 初始化一个长度为 n+1 的数组 dp，其中 n 是给定的正整数，dp[i] 表示组成整数 i 所需要的最少的完全平方数的数量。将 dp[0] 设置为 0，因为组成整数 0 不需要任何完全平方数。

2. 对于 i 从 1 到 n，计算 dp[i]：

   • 初始化 dp[i] 为无穷大（例如 Integer.MAX_VALUE）。
   • 对于每一个完全平方数 j，如果 j <= i，那么 dp[i] = min(dp[i], dp[i - jj] + 1)。意思是，如果我们可以通过添加一个 j 来组成 i，那么我们就可以在组成 i - j*j 所需要的完全平方数的数量的基础上加一，得到组成 i 所需要的完全平方数的数量。

3. 返回 dp[n]，这就是组成给定正整数所需要的最少的完全平方数的数量。

代码实现

• 暴力法

  const max = Math.floor(Math.sqrt(n));
  const squares = Array.from({ length: max }, (_, i) => (i + 1) ** 2);
  function dfs(n: number, depth: number): number {
    if (n === 0) return depth;
    let min = Infinity;
    for (let i = 0; i < squares.length; i++) {
      if (n - squares[i] >= 0) {
        min = Math.min(min, dfs(n - squares[i], depth + 1));
      }
    }
    return min;
  }
  return dfs(n, 0);

• 动规法

  const dp = Array.from({ length: n + 1 }, () => Infinity);
  dp[0] = 0;
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j * j <= i; j++) {
      //在所有可能的分解方式中，选择最少的完全平方数的和
      dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
    }
  }
  return dp[n];