最小的理想平方数，在JavaScript中总计为n

  • Z时代
  • 2024-01-10
  • 分类：综合

我们需要编写一个以正数（例如num）作为唯一参数的JavaScript函数。

该函数应找到这样的完美平方数的组合，将其相加后得出所提供的数字作为输入。我们必须使我们尽可能少地使用完美正方形。

例如-

如果输入号码是-

const num = 123;

那么输出应该是-

const output = 3;

因为123 = 121 +1 + 1

这是一个经典的动态规划问题，我们可以根据其先前编号的结果来得出特定编号的结果。

在直接进入代码之前，让我们首先尝试了解一种通用模式，以及DP实际上将如何帮助我们设计解决方案。

六个五个数字的结果将是-

1 --> 1 (1)
2 --> 2 (1 + 1)
3 --> 3 (1 + 1 + 1)
4 --> 1 (4)
5 --> 2 (4 + 1)
6 --> 3 (4 + 1 + 1)

这清楚地表明，我们必须尝试将先前的结果组合起来才能获得后续的结果。

示例

以下是代码-

const num = 123;
const sumSquares = (num) => {
   let arr = new Array(num + 1).fill(0);
   arr[1] = 1;
   for(let i = 1; i * i <= num; i++) {
      for(let j = i * i; j < arr.length; j++) {
         if(arr[j] == 0) {
            arr[j] = arr[j - (i * i)] + 1;
         } else {
            arr[j] = Math.min(arr[j - (i * i)] + 1, arr[j]);
         }
      }
   };
   return arr[num];
};
console.log(sumSquares(num));
输出结果

以下是控制台输出-

3

以上是 最小的理想平方数，在JavaScript中总计为n 的全部内容， 来源链接： utcz.com/z/337251.html

回到顶部