Đường đi tổng nhỏ nhất trong JavaScript

Mô tả vấn đề

Hàm JavaScript nhận vào mảng 2D số làm đối số duy nhất. Hàm tìm các đường đi bằng cách chọn đúng một phần tử từ mỗi hàng, và không có hai phần tử từ hàng liền kề nào ở cùng cột. Trong tất cả các đường đi đó, hàm trả về tổng của đường đi có tổng nhỏ nhất.

Ví dụ, nếu đầu vào là:

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

Thì đầu ra nên là:

const output = 9;

Giải thích đầu ra

Tất cả đường đi hợp lệ và tổng của chúng. Đường đi [1, 2, 6] có tổng nhỏ nhất = 9.

Ví dụ minh họa

Mã thực hiện (DP bottom-up, chỉ giữ 2 giá trị nhỏ nhất mỗi hàng):

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

Kết quả trong console sẽ là:

9