การเขียนโปรแกรมแบบไดนามิก - ผลรวมขององค์ประกอบ 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) space.

ตัวอย่าง

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 ]