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

เราจำเป็นต้องเขียนฟังก์ชัน JavaScript ที่ใช้จำนวนบวก เช่น num เป็นอาร์กิวเมนต์เดียว

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

ตัวอย่างเช่น −

หากหมายเลขอินพุตคือ −

const num = 123;

จากนั้นผลลัพธ์ควรเป็น −

const output = 3;

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

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

ก่อนข้ามไปที่โค้ด ให้พยายามทำความเข้าใจรูปแบบทั่วไปก่อน และว่าจริง ๆ แล้ว 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));

ผลลัพธ์

ต่อไปนี้เป็นเอาต์พุตคอนโซล -