JavaScript 中具有最小總和的路徑

問題

JavaScript 函式採用二維陣列作為第一個且唯一一個引數。

函式應透過從二維陣列中選取每個行的恰好一個元素尋找路徑，且相鄰行的選取元素不能在同一列。在所有這些路徑中，我們的函式應返回和最小的路徑。

例如，若輸入函式 −

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

則輸出應為 −

const output = 9;

輸出說明

因為所有有效路徑為 −

而在所有這些路徑中，[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));

輸出

控制檯的輸出將為 −

9

AmitDiwan

更新日期： 07-Apr-2021

222 次瀏覽

開啟您的 職業生涯

透過完成課程獲得認證

開始使用