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 次浏览

开启您的 职业生涯

通过完成课程获得认证

开始使用