資料結構
網路
關係型資料庫管理系統 (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 次瀏覽
廣告