จำนวนน้อยที่สุดของกำลังสองสมบูรณ์ที่รวมกันได้ n ใน JavaScript

เราต้องเขียนฟังก์ชัน JavaScript ที่รับจำนวนบวก num เป็นอาร์กิวเมนต์เดียว ฟังก์ชันต้องหาการรวมของตัวเลขกำลังสองสมบูรณ์ที่เมื่อบวกกันแล้วได้ตัวเลขนำเข้า โดยใช้จำนวนกำลังสองให้น้อยที่สุดเท่าที่จะเป็นไปได้

ตัวอย่าง

ถ้าตัวเลขนำเข้าคือ:

const num = 123;

ผลลัพธ์ควรเป็น:

const output = 3;

เพราะ 123 = 121 + 1 + 1

นี่เป็นปัญหา Dynamic Programming คลาสสิก ที่เราสามารถหาคำตอบสำหรับตัวเลขใดตัวหนึ่งจากผลลัพธ์ของตัวเลขก่อนหน้า

ตัวอย่างโค้ด

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));