เส้นทางที่มีผลรวมน้อยที่สุดใน JavaScript

ปัญหา

ฟังก์ชัน JavaScript ที่รับอาร์เรย์ 2 มิติของตัวเลขเป็นอาร์กิวเมนต์แรกและอาร์กิวเมนต์เดียว

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

ตัวอย่างเช่น หากอินพุตของฟังก์ชันคือ −

const arr = [
   [4, 7, 1],
   [2, 8, 3],
   [5, 6, 9]
]

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

const output = 9;

คำอธิบายผลลัพธ์

เพราะทุกเส้นทางที่ถูกต้องคือ −

4, 8, 9	4, 8, 6	4, 3, 6	4, 3, 5
7, 2, 6	7, 2, 9	7, 3, 6	7, 3, 5
1, 2, 6	1, 2, 9	1, 8, 9	1, 8, 5

และจากทั้งหมดเหล่านี้ [1, 2, 6] มีผลรวมน้อยที่สุดที่ 9

ตัวอย่าง

รหัสสำหรับสิ่งนี้จะเป็น −

const arr = [
   [4, 7, 1],
   [2, 8, 3],
   [5, 6, 9]
]
const minimumPathSum = (arr = []) => {
   let first = [0, null];
   let second = [0, null];
   for(let row = arr.length - 1; row >= 0; row--){
      let curr1 = null;
      let curr2 = null;
      for(let column = 0; column < arr[row].length; column++){
         let currentSum = arr[row][column];
         if(column !== first[1]){
            currentSum += first[0];
         }else{
            currentSum += second[0];
         };
         if(curr1 === null || currentSum < curr1[0]){
            curr2 = curr1;
            curr1 = [currentSum, column];
         }else if(curr2 === null || currentSum < curr2[0]){
            curr2 = [currentSum, column];
         };
      };
      first = curr1;
      second = curr2;
   };
   return first[0];
};
console.log(minimumPathSum(arr));

ผลลัพธ์

และผลลัพธ์ในคอนโซลจะเป็น −