Dynamic Programming - ผลรวมส่วนของสมาชิกใน JavaScript

สมมติว่าเรามีอาร์เรย์ของตัวเลขแบบนี้:

const arr = [1, 2, 3, 4, 5];

การนำสมาชิกน้อยลงทีละตัว อาร์เรย์นี้สามารถแยกออกได้แบบนี้:

[1, 2, 3, 4, 5] [2, 3, 4, 5] [3, 4, 5] [4, 5] [5] []

เราต้องเขียนฟังก์ชัน JavaScript ที่รับอาร์เรย์ดังกล่าว ฟังก์ชันควรแยกอาร์เรย์ในลักษณะเดียวกับที่อธิบายข้างต้น ฟังก์ชันควรสร้างอาร์เรย์ที่มีผลรวมของส่วนเหล่านั้นและคืนค่าอาร์เรย์นั้น ดังนั้น สำหรับอาร์เรย์นี้ ผลลัพธ์ควรเป็นดังนี้:

const output = [15, 14, 12, 9, 5 0];

เราจะใช้ Dynamic Programming เพื่อแก้ปัญหานี้ เราจะคำนวณผลรวมของอาร์เรย์ทั้งหมดในเวลา O(n) ก่อน ซึ่งจะกลายเป็นสมาชิกแรกของอาร์เรย์ แล้วในรอบวนซ้ำอีกครั้ง เราจะลบสมาชิกที่สอดคล้องกันไปเรื่อยๆ เพื่อได้สมาชิกของอาร์เรย์ผลลัพธ์ วิธีนี้เราสามารถแก้ปัญหาได้ในเวลา O(n) และพื้นที่ O(1)

ตัวอย่าง

const arr = [1, 2, 3, 4, 5];
const sumArray = (arr = []) => arr.reduce((a, b) => a + b, 0);
const partialSum = (arr = []) => {
  let sum = sumArray(arr);
  const res = [sum];
  for(let i = 0; i < arr.length; i++){
    const el = arr[i];
    sum -= el;
    res.push(sum);
  };
  return res;
};
console.log(partialSum(arr));

ผลลัพธ์

สิ่งนี้จะให้ผลลัพธ์ดังนี้:

[ 15, 14, 12, 9, 5, 0 ]