Đường dẫn có tổng nhỏ nhất trong JavaScript

Vấn đề

Hàm JavaScript nhận mảng số 2-D làm đối số đầu tiên và duy nhất.

Hàm của chúng ta sẽ tìm các đường dẫn từ mảng 2-D bằng cách chọn chính xác một phần tử từ mỗi hàng và không có hai phần tử nào được chọn từ các hàng liền kề phải nằm trong cùng một cột. Trong số tất cả các đường dẫn này, hàm của chúng ta sẽ trả về tổng của đường dẫn đó có tổng là nhỏ nhất.

Ví dụ:nếu đầu vào của hàm là -

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

Sau đó, đầu ra phải là -

const output = 9;

Giải thích đầu ra

Bởi vì tất cả các đường dẫn hợp lệ là -

Và trong số tất cả, [1, 2, 6] có tổng ít nhất là 9.

Ví dụ

Mã cho điều này sẽ là -

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

Đầu ra

Và đầu ra trong bảng điều khiển sẽ là -

9