下降路径最小和-931

[sl1673495]

给定一个方形整数数组  A，我们想要得到通过 A 的下降路径的最小和。

下降路径可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列。

示例：

输入：[[1,2,3],[4,5,6],[7,8,9]]
输出：12
解释：
可能的下降路径有：
[1,4,7], [1,4,8], [1,5,7], [1,5,8], [1,5,9]
[2,4,7], [2,4,8], [2,5,7], [2,5,8], [2,5,9], [2,6,8], [2,6,9]
[3,5,7], [3,5,8], [3,5,9], [3,6,8], [3,6,9]
和最小的下降路径是 [1,4,7]，所以答案是 12。

提示：

1 <= A.length == A[0].length <= 100 -100 <= A[i][j] <= 100

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/minimum-falling-path-sum 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

题目列出了所有的下降路径，所以一开始有些误导到我去用了递归回溯法暴力求解，果不其然超时了。

其实应该用动态思路，从下往上求解，某一个格子的向下最小路径确定以后，上一行就可以直接利用下一行中这个格子的最小路径去继续求解了。

状态转移方程： dp[i][j] = min(dp[i + 1][j - 1], dp[i + 1][j], dp[i + 1][j + 1])

/**
 * @param {number[][]} A
 * @return {number}
 */
let minFallingPathSum = function (A) {
  let n = A.length

  let dp = []
  for (let i = 0; i < n; i++) {
    dp[i] = []
  }

  for (let j = 0; j < n; j++) {
    dp[n - 1][j] = A[n - 1][j]
  }

  for (let i = n - 2; i >= 0; i--) {
    for (let j = 0; j < n; j++) {
      dp[i][j] = Infinity
      let left = j - 1
      let right = j + 1
      let mid = j
      let nextRowIndexes = [left, mid, right]
      for (let nextRowIndex of nextRowIndexes) {
        if (nextRowIndex >= 0 && nextRowIndex < n) {
          dp[i][j] = Math.min(dp[i][j], A[i][j] + dp[i + 1][nextRowIndex])
        }
      }
    }
  }

  // 第一行的最小值 可以确定整体的最小路径
  return Math.min(...dp[0])
}

[cwjbjy]

内存击败100%

var minFallingPathSum = function (matrix) {
    let n = matrix.length;

    for (let i = 1; i < n; i++) {
        for (let j = 0; j < n; j++) {
            //处理边界
            if (j === 0) {
                //左边界
                matrix[i][j] += Math.min(matrix[i - 1][j], matrix[i - 1][j + 1]);
            } else if (j === n - 1) {
                //右边界
                matrix[i][j] += Math.min(matrix[i - 1][j - 1], matrix[i - 1][j]);
            } else {
                matrix[i][j] = matrix[i][j] + Math.min(matrix[i - 1][j - 1], matrix[i - 1][j], matrix[i - 1][j + 1]);
            }
        }
    }

    return Math.min(...matrix[n - 1])
};

[huanzheke]

function getMinsum(sum, arr){ const current = arr[0]; let num = Infinity; for(let i=0;i<current.length; i++){ if(current[i] < num){ num = current[i]; } } if(arr.length > 1){ sum = getMinsum(sum + num, arr.slice(1)); }else{ sum += num; } return sum; }

[keer-tea]

内存击败100%

var minFallingPathSum = function (matrix) {
    let n = matrix.length;

    for (let i = 1; i < n; i++) {
        for (let j = 0; j < n; j++) {
            //处理边界
            if (j === 0) {
                //左边界
                matrix[i][j] += Math.min(matrix[i - 1][j], matrix[i - 1][j + 1]);
            } else if (j === n - 1) {
                //右边界
                matrix[i][j] += Math.min(matrix[i - 1][j - 1], matrix[i - 1][j]);
            } else {
                matrix[i][j] = matrix[i][j] + Math.min(matrix[i - 1][j - 1], matrix[i - 1][j], matrix[i - 1][j + 1]);
            }
        }
    }

    return Math.min(...matrix[n - 1])
};

不错的思路