数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学JavaScript 中将最少数量的完全平方数相加得到 n
我们需要编写一个 JavaScript 函数，它只接受一个正数 num 作为参数。
该函数应该找到这样一些完全平方数的组合，这些数相加等于输入的数字。我们必须确保使用尽可能少的完全平方数。
例如：
如果输入数字为：
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
更新于：2021年1月22日
214 次浏览
广告