base case 和备忘录的初始值怎么定？ :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：base case 和备忘录的初始值怎么定？

评论礼仪 见这里，违者直接拉黑。

[xiaoxu-git]

东哥，我有一个问题不是很明白，之前框架的思路是：明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义。但是这个题却说得是：base case是根据 dp 函数的定义所决定的。这个该怎么理解呢？

[process-sk]

memo[i][j] = matrix[i][j] + min( dp(matrix, i - 1, j), dp(matrix, i - 1, j - 1), dp(matrix, i - 1, j + 1) );中的matrix[i][j]会不会被重复计算呢

[deepbreath373]

memo[i][j] = matrix[i][j] + min( dp(matrix, i - 1, j), dp(matrix, i - 1, j - 1), dp(matrix, i - 1, j + 1) );中的matrix[i][j]会不会被重复计算呢

所以代码中使用了备忘录memo[][]数组来避免，如果matrix[i][j]计算过，就已经把结果存入到memo[i][j]。 下次直接判断memo对应的值是不是设定的特殊值就知道有没有计算过了，如果计算过就直接返回就好了。

if (memo[i][j] != 66666) {
      return memo[i][j];
}

[tsfans]

这样写感觉比较好理解,跟题目逻辑保持一致

   /**
     * 状态转移方程,对于nums[row][col]这个位置,其最小下降路径和为:
     * dp[row][col] = nums[row][col] + Math.min(nums[row+1][col-1], nums[row+1][col], nums[row+1][col+1])
     * base case为落到底时,注意检查col是否越界
     * TC=O(N^2),SC=O(N^2)
     */
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;
        dp = new int[n+1][n+1];
        for(int[] d : dp){
            // 初始化dp数组
            Arrays.fill(d, Integer.MAX_VALUE);
        }
        int min = Integer.MAX_VALUE;
        for(int i = 0; i < n; i++){
            // 逐个计算第一行的每个元素的最小下降路径和,取最小的一个
            min = Math.min(min, matrix(matrix, 0, i));
        }
        return min;
    }

    int[][] dp;

    int matrix(int[][] matrix, int row, int col){
        int n = matrix.length;
        // base case
        // 列越界
        if(col < 0 || col >= n) return Integer.MAX_VALUE;
        // 落到底
        if(row == n - 1) return matrix[row][col];
        // 查询备忘录
        if(dp[row][col] != Integer.MAX_VALUE) return dp[row][col];
        int res = matrix[row][col] + Math.min(Math.min(matrix(matrix, row+1, col-1), matrix(matrix, row+1, col)),       
                                              matrix(matrix, row+1, col+1));
        // 保存结果到备忘录
        dp[row][col] = res;
        return res;
    }

[tsfans]

格式化一下代码

   /**
     * 状态转移方程,对于nums[row][col]这个位置,其最小下降路径和为:
     * dp[row][col] = nums[row][col] + Math.min(nums[row+1][col-1], nums[row+1][col], nums[row+1][col+1])
     * base case为落到底时,注意检查col是否越界
     * TC=O(N^2),SC=O(N^2)
     */
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;
        dp = new int[n+1][n+1];
        for(int[] d : dp){
            // 初始化dp数组
            Arrays.fill(d, Integer.MAX_VALUE);
        }
        int min = Integer.MAX_VALUE;
        for(int i = 0; i < n; i++){
            // 逐个计算第一行的每个元素的最小下降路径和,取最小的一个
            min = Math.min(min, matrix(matrix, 0, i));
        }
        return min;
    }

    int[][] dp;

    int matrix(int[][] matrix, int row, int col){
        int n = matrix.length;
        // base case
        // 列越界
        if(col < 0 || col >= n) return Integer.MAX_VALUE;
        // 落到底
        if(row == n - 1) return matrix[row][col];
        // 查询备忘录
        if(dp[row][col] != Integer.MAX_VALUE) return dp[row][col];
        int res = matrix[row][col] + Math.min(Math.min(matrix(matrix, row+1, col-1), matrix(matrix, row+1, col)),       
                                              matrix(matrix, row+1, col+1));
        // 保存结果到备忘录
        dp[row][col] = res;
        return res;
    }

[Tokics]

这道题和之前之后的的文章有点不一样，之前都是dp[]或dp[][]，为什么这里要用一个函数呢？为什么不用二维dp数组呢？什么时候该用函数呢？

[labuladong]

@Tokics 你仔细看「动态规划核心框架」这篇文章，函数和数组是一样的，自顶向下和自底向上的区别而已。

[zhongweiLeex]

贴一个很暴力的动态规划 提示：

• 关于 循环中的判断可以拿到循环外面 作为base case 讨论

• 此处最需要考虑的一个情况就是在第 n - 1 列的时候， 只能从左上角 或者正上方下降，不能从右上方下降了

  class Solution {
  public int minFallingPathSum(int[][] matrix) {
      int[][] dp = new int[matrix.length][matrix[0].length];
      int min = Integer.MAX_VALUE;
      if(matrix.length == 1){
          return matrix[0][0];
      }
  
      for(int i = 0; i<matrix.length ; i++){
          for(int j = 0; j<matrix[0].length; j++){
              if(i == 0){
                  dp[i][j] = matrix[i][j];
              }else if (j == 0){
                  dp[i][j] = matrix[i][j] + Math.min(dp[i-1][j],dp[i-1][j+1]);
              }else if(j == matrix.length-1){
                  dp[i][j] = matrix[i][j] + Math.min(dp[i-1][j],dp[i-1][j-1]);
              }else{
                  dp[i][j] =  Math.min(Math.min(dp[i-1][j+1],dp[i-1][j]),dp[i-1][j-1])+matrix[i][j];
              }
              if(i == matrix.length-1){
                  min = Math.min(min,dp[i][j]);
              }
          }
      }
      return min;
  }
  }

[CFCode-git]

补一个dp数组解法：

function minFallingPathSum(matrix: number[][]): number {
  let boundry = matrix.length // 方形数组边界

  // 辅助函数
  const min = (...args:number[]):number => {
    let vals = args.filter(Boolean)
    let res = vals[0]
    for(let i = 1; i < vals.length; i++){
      if(vals[i]<res)res = vals[i]
    }
    return res
  }

  let res = Number.MAX_SAFE_INTEGER

  let dp = new Array(boundry)
  for(let i = 0; i < dp.length; i++){
    dp[i] = new Array(boundry).fill(0)
  }

  for(let i = 0; i < boundry; i++){
    for(let j = 0; j < boundry; j++){
      if(i===0){
         dp[i][j] = matrix[i][j]
      }else{
        if(j-1<0){
          dp[i][j] = matrix[i][j] + min(dp[i-1][j],dp[i-1][j+1])
        }else if(j+1>boundry){
          dp[i][j] = matrix[i][j] + min(dp[i-1][j-1],dp[i-1][j])
        }else{
          dp[i][j] = matrix[i][j] + min(dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1])
        }
      }
    }
  }
  return min(...dp[boundry-1])
};

[renlindong]

贴个dp数组解法，重新发一下，刚刚那个代码高亮😂

function minFallingPathSum(matrix: number[][]): number {
  if(matrix.length === 0) {
    return 0
  }
  const MAX = 100 * 100 + 1
  const m = matrix.length
  const n = matrix[0].length
  const dp = new Array(m + 1)
  dp[0] = new Array(n + 2).fill(0)
  for(let i = 1; i < dp.length; i++) {
    if(dp[i] === undefined) {
      dp[i] = new Array(n + 2).fill(MAX)
    }
    for(let j = 1; j <= n; j++) {
      dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i - 1][j + 1]) + matrix[i - 1][j - 1]
    }
  }
  return Math.min(...dp[dp.length - 1])
};

[TomCN0803]

#include <vector>

#define MAX_LIMIT 10000

using namespace std;

int minFallingPathSum(vector<vector<int>> &matrix) {
    const auto m = matrix.size(), n = matrix[0].size();
    vector<vector<int>> dp(m, vector<int>(n));
    for (auto i = 0; i < m; i++) {
        for (auto j = 0; j < n; j++) {
            if (!i) {
                dp[i][j] = matrix[i][j];
                continue;
            }
            dp[i][j] = dp[i - 1][j] + matrix[i][j];
            if (j - 1 >= 0)
                dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + matrix[i][j]);
            if (j + 1 < n)
                dp[i][j] = min(dp[i][j], dp[i - 1][j + 1] + matrix[i][j]);
        }
    }

    int res = MAX_LIMIT;
    for (auto x: dp[m - 1])
        res = min(res, x);

    return res;
}

[libxing]

c++超时，思路就是一模一样的思路，代码如下：

class Solution {
public:
    vector<vector<int>> memo;//备忘录

    int minFallingPathSum(vector<vector<int>> matrix) {
        int n = matrix.size();
        int res = INT_MAX;

        //备忘录初试化为特殊值666666
        memo.resize(n);
        fill(memo.begin(), memo.end(), vector<int>(n, 666666));

        for (int j = 0; j < n; j++) {
            // 终点可能在 matrix[n-1] 的任意一列
            res = min(res, dp(matrix, n - 1, j));
        }
        return res;
    }

    inline int dp(vector<vector<int>> matrix, int i, int j) {
        int n = matrix.size();
        //非法索引检查
        if (i < 0 || j < 0 ||
            i >= n ||               //注意这里是大于等于
            j >= matrix[0].size())
        {
            return 999999;//返回一个特殊值
        }

        //base case
        if (i == 0) {
            return matrix[i][j];
        }

        //查备忘录。防止重复计算
        if (memo[i][j] != 666666) {
            return memo[i][j];
        }

        //状态转移，并且将计算的结果存入备忘录
        memo[i][j] = matrix[i][j] + min(dp(matrix, i - 1, j),
            min(dp(matrix, i - 1, j - 1), dp(matrix, i - 1, j + 1)));
        return memo[i][j];
    }
};

[labuladong]

@q240627995 递归函数的数组参数传引用

[libxing]

@q240627995 递归函数的数组参数传引用

完美解决！感谢！！！学以致用，理论结合实际真的很重要！面经背的很熟：引用减少开销、可以修改数组内部值巴拉巴拉，实际coding时却常常忘记引用传入！

[hezhu1996]

贴一个好理解的数组解法

class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;

        int[][] dp = new int[m][n];

        // base case
        for(int i = 0; i < n; i++){
            dp[0][i] = matrix[0][i];
        }

        for(int i = 1; i < m; i++){
            for(int j = 0; j < n; j++){
                if(j < 1){
                    dp[i][j] = matrix[i][j] + Math.min(dp[i - 1][j], dp[i - 1][j + 1]);
                }
                else if(j >= n - 1){
                    dp[i][j] = matrix[i][j] + Math.min(dp[i - 1][j], dp[i - 1][j - 1]);
                }
                else{
                    dp[i][j] = matrix[i][j] + getMin(dp[i - 1][j], dp[i - 1][j - 1], dp[i - 1][j + 1]);
                }
            }
        }

        int min = Integer.MAX_VALUE;
        for(int i = 0; i < n; i++){
            min = Math.min(min, dp[m - 1][i]);
        }

        return min;
    }

    public int getMin(int a, int b, int c){
        return Math.min(a, Math.min(b, c));
    }
}

[Goolloo]

Java Compressed DP "Table"

class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int height = matrix.length;
        int width = matrix[0].length;

        int[] sums = new int[width];
        int[] previousSums = new int[width];
        for(int i = 0; i < width; i++) {
            previousSums[i] = matrix[0][i];
        }

        for(int i = 1; i < height; i++) {
            for(int j = 0; j < width; j++) {
                int previousSum = previousSums[j];
                if(j-1 >= 0) {
                    previousSum = Math.min(previousSum, previousSums[j-1]);
                }

                if(j+1 < width) {
                    previousSum = Math.min(previousSum, previousSums[j+1]);
                }

                sums[j] = matrix[i][j] + previousSum;
            }

            previousSums = sums;
            sums = new int[width];
        }

        int min = Integer.MAX_VALUE;
        for(int i = 0; i < width; i++) {
            min = Math.min(min, previousSums[i]);
        }

        return min;
    }
}

[bert82503]

打卡，感谢楼主！

[d0odLe]

来一个用初始化dp数组规避边界判断的写法

class Solution {
    // dp定义：以i,j元素结尾的元素经过的最短路径总长度
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;
        // 左右两边边界扩宽1，简化边界处理
        int[][] dp = new int[n][n+2];
        // 初始化数组全部填充最大值(本题找的是最小值)
        for (int[] dprow : dp){
            Arrays.fill(dprow, Integer.MAX_VALUE);
        }
        // 拷贝首行，从第1列开始，拷贝n个数
        System.arraycopy(matrix[0], 0, dp[0], 1, n);

        for (int i = 1; i < n; i ++){
            for (int j = 1; j < n+1; j ++){
                // 注意由于j表示的是向右偏移1列后的位置，在加上matrix的值时需要左偏移一位还原 matrix[i][j-1]
                dp[i][j] = smaller(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]) + matrix[i][j-1];
            }
        }

        // 在最后一行找最小值即为答案
        int res = Integer.MAX_VALUE;
        for (int i = 1; i < n+1; i ++){
            res = Math.min(res, dp[n-1][i]);
        }

        return res;
    }

    int smaller(int a, int b, int c) {
        return Math.min(a, Math.min(b, c));
    }
}

[LebronHarden1]

我感觉还是先找到dp数组或者函数的定义,然后找状态转移方程,然后初始条件这样一个顺序比较好,上来就base case,连dp的定义都没明白,咋base case

[Maxiah]

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        // dp
        int m = matrix.size(); // 行
        int n = matrix[0].size(); // 列
        // dp[i][j]:从maxtrix[0][..]开始下落，落到maxtrix[i][j]的最小和为dp[i][j]
        // 因此dp数组的大小也是m x n，里面存储的是到达maxtrix[i][j]的下降路径最小和
        vector<vector<int>> dp(m,vector<int>(n, INT_MAX));

        // base case: dp[0][j]
        for(int j = 0; j < n; j++){
            dp[0][j] = matrix[0][j];
        }

        for(int i = 1; i < m; i++){
            for(int j = 0; j < n; j++){
                // dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]) + matrix[i][j];
                // 分批处理
                // dp[i-1][j]
                dp[i][j] = dp[i-1][j] + matrix[i][j];
                // dp[i-1][j-1]
                if(j - 1 >= 0){
                    dp[i][j] = min(dp[i][j], dp[i-1][j-1] + matrix[i][j]);
                }
                // dp[i-1][j+1]
                if(j + 1 < n){
                    dp[i][j] = min(dp[i][j], dp[i-1][j+1] + matrix[i][j]);
                }

            }
        }

        int res = INT_MAX;
        for(auto x : dp[m-1]){
            res = min(res, x);
        }
        return res;
    }
};

[gaozhanting]

import Foundation

class Solution {
    func minFallingPathSum(_ matrix: [[Int]]) -> Int {
        return dp(matrix, matrix[0], matrix.count)
    }

    // input: matrix, choices
    // output: 下降路径最小和 of matrix；并且限定只能在choices中做选择
    func dp(_ matrix: [[Int]], _ choices: [Int], _ w: Int) -> Int {
        if matrix.isEmpty { return 0 }

        let nMatrix = Array(matrix.dropFirst())

        var res = Int.max
        for (index, value) in choices.enumerated() {
            func fn() -> [Int] {
                if nMatrix.isEmpty {
                    return []
                }
                let choiceRow = nMatrix[0]
                if index == 0 {
                    return [choiceRow[index], choiceRow[index + 1]]
                } else if index == w - 1 {
                    return [choiceRow[index - 1], choiceRow[index]]
                } else {
                    return [choiceRow[index - 1], choiceRow[index], choiceRow[index + 1]]
                }
            }

            let nextChoices = fn()

            res = min(res, dp(nMatrix, nextChoices, w) + value)
        }

        return res
    }
}

print(Solution().minFallingPathSum([[2,1,3],[6,5,4],[7,8,9]]))

[oliyg]

我觉得我好想会了，有点感觉了，下面是我贴的 js 的数组代码，各位大佬们看看有啥问题不：

/**
 * @param {number[][]} matrix
 * @return {number}
 */
var minFallingPathSum = function (matrix) {
  const rows = matrix.length;
  const cols = rows;

  // 1. dp
  const dp = new Array(rows)
    .fill(Number.MAX_SAFE_INTEGER)
    .map(() => new Array(cols).fill(Number.MAX_SAFE_INTEGER));
  // 2. init
  for (let col = 0; col < cols; col++) {
    dp[0][col] = matrix[0][col];
  }
  // 3. for
  for (let row = 1; row < rows; row++) {
    for (let col = 0; col < cols; col++) {
      // 4. choose
      // 当前位置可以从上方三个方向转移过来
      const top = dp[row - 1][col] ?? Number.MAX_SAFE_INTEGER;
      const tl = dp[row - 1][col - 1] ?? Number.MAX_SAFE_INTEGER;
      const tr = dp[row - 1][col + 1] ?? Number.MAX_SAFE_INTEGER;
      dp[row][col] = matrix[row][col] + Math.min(top, tl, tr);
    }
  }

  return Math.min(...dp[dp.length - 1]);
};

[aizigao]

感谢东哥，我也写出来了，自底向上的

class Solution:
    # 自底向上
    '''
   matrix 
    [
     [2, 1, 3], 
     [6, 5, 4], 
     [7, 8, 9]
    ]

   dp
   [
      [99999, 2, 1, 3, 99999],
      [99999, 7, 6, 5, 99999],
      [99999, 13, 13, 14, 99999]
   ]
    '''
    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        n = len(matrix)
        '''
        dp数组 边界左右填充为99999， 避免边界
        '''
        dp = [[99999] * (n + 2) for i in range(n)]

        # base case 第一行填充为 matrix一样
        for j in range(n):
            k = j + 1
            dp[0][k] = matrix[0][j]

        for i in range(1, n):
            for j in range(n):
                # 0 和 n 列为 9999
                k = j + 1
                dp[i][k] = min(dp[i - 1][k - 1], dp[i - 1][k],
                               dp[i - 1][k + 1]) + matrix[i][j]
        res = float('inf')
        # 0 和 n 列为 9999, 结果为最后一行的最小值
        for k in range(1, n + 1):
            res = min(dp[n - 1][k], res)
        return res

[zhongweiLeex]

基本情况还是和我上面的帖子类似， 其实就是要看不同位置的情况

class Solution {
    public int minFallingPathSum(int[][] matrix) {

        int n = matrix.length;
        if(n == 1){
            return matrix[0][0];
        }

        int min = Integer.MAX_VALUE;
        int[][] dp = new int[n][n]; // dp[i][j] 表示 从 第一行的某个元素到当前位置i,j下降路径的最小和

        //初始化第一行的值
        for(int j = 0; j<n;j++){
            dp[0][j] = matrix[0][j];//第一行到达第一行的所有元素的最小路径的和就是自己 
        }

        for(int i = 1 ; i<n;i++){
            for(int j = 0; j<n;j++){
                if(j == 0){ //第一列 只能从正上方 或者 右上角 到达
                    dp[i][j] = Math.min(dp[i-1][j],dp[i-1][j+1]) + matrix[i][j];
                }else if( j == n-1){//最后一列， 只能从正上方 或者 左上角到达
                    dp[i][j] = Math.min(dp[i-1][j],dp[i-1][j-1]) + matrix[i][j];
                }else{
                    dp[i][j] = Math.min(Math.min(dp[i-1][j+1],dp[i-1][j]),dp[i-1][j-1]) + matrix[i][j];
                }
                //到达最后一行了 进行一个更新动作
                if(i == n-1){
                    min = Math.min(min,dp[i][j]);
                }
            }
        }
        return min;
    }
}

[lhcezx]

C++贴一个精简版本的DP数组

class Solution {
    vector<vector<int>> dp_table;                       //  记录在每一个位置[i, j]的下降最小路径和
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int n = matrix.size();
        dp_table.resize(n, vector<int> (n, INT_MAX));
        for (int i = 0; i < n; i++) {                   //  base case
            dp_table[0][i] = matrix[0][i];
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int left = j - 1 >= 0? dp_table[i - 1][j - 1]: INT_MAX;
                int mid = dp_table[i - 1][j];
                int right = j + 1 < n? dp_table[i - 1][j + 1]: INT_MAX;
                dp_table[i][j] = min(left, min(mid, right)) + matrix[i][j];
            }
        }
        int res = INT_MAX;
        for (int j = 0; j < n; j++) {
            res = min(res, dp_table[n - 1][j]);
        }
        return res;
    }
};

[deepbreath373]

check in

[guqihao-7]

感谢东哥，第一次自己独立做出来的dp，从暴力递归，到利用备忘录记忆化搜索，到dp填表，代码如下： 暴力递归：

class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < matrix.length; i++) {
            ans = Math.min(ans, process(matrix, 0, i));
        }
        return ans;
    }

    public int process(int[][] matrix, int row, int column) {
        if (column >= matrix.length || column < 0
                || row >= matrix.length || row < 0) {
            return 0;
        }

        if (column == 0) {
            int temp = Math.min(process(matrix, row + 1, column),
                            process(matrix, row + 1, column + 1));
            return matrix[row][column] + temp;
        }

        if (column == matrix.length - 1) {
            int temp = Math.min(process(matrix, row + 1, column),
                            process(matrix, row + 1, column - 1));
            return matrix[row][column] + temp;
        }

        int temp = Math.min(process(matrix, row + 1, column),
                        Math.min(process(matrix, row + 1, column + 1),
                                process(matrix, row + 1, column - 1)));
        return matrix[row][column] + temp;
    }
}

备忘录 记忆化搜索：

class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int ans = Integer.MAX_VALUE;
        dp = new int[matrix.length][matrix[0].length];
        for (int i = 0; i < dp.length; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        for (int i = 0; i < dp[dp.length - 1].length; i++) {
            dp[dp.length - 1][i] = matrix[dp.length - 1][i];
        }
        for (int i = 0; i < matrix.length; i++) {
            ans = Math.min(ans, process(matrix, 0, i));
        }
        return ans;
    }

    int[][] dp;

    public int process(int[][] matrix, int row, int column) {
        if (column >= matrix.length || column < 0
                || row >= matrix.length || row < 0) {
            return 0;
        }

        if (dp[row][column] != Integer.MAX_VALUE) {
            return dp[row][column];
        }

        if (column == 0) {
            int temp = Math.min(process(matrix, row + 1, column),
                            process(matrix, row + 1, column + 1));
            dp[row][column] = matrix[row][column] + temp;
            return dp[row][column];
        }

        if (column == matrix.length - 1) {
            int temp = Math.min(process(matrix, row + 1, column),
                            process(matrix, row + 1, column - 1));
            dp[row][column] = matrix[row][column] + temp;
            return dp[row][column];
        }

        int temp = Math.min(process(matrix, row + 1, column),
                        Math.min(process(matrix, row + 1, column + 1),
                                process(matrix, row + 1, column - 1)));
        dp[row][column] = matrix[row][column] + temp;
        return dp[row][column];
    }
}

class Solution {
    public int minFallingPathSum(int[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return -1;
        }
        return process(matrix);
    }

    public int process(int[][] matrix) {
        int[][] cache = new int[matrix.length][matrix[0].length];
        for (int i = 0; i < cache[cache.length - 1].length; i++) {
            cache[cache.length - 1][i] = matrix[matrix.length - 1][i];
        }

        int firstColumn = 0;
        int lastColumn = cache.length - 1;

        for (int row = cache.length - 2; row >= 0; row--) {
            for (int column = 0; column < cache[row].length; column++) {

                if (column == firstColumn) {
                    cache[row][0] = matrix[row][0] + Math.min(cache[row + 1][0], cache[row + 1][1]);
                    continue;
                }

                if (column == lastColumn) {
                    cache[row][lastColumn] = matrix[row][lastColumn] +
                            Math.min(cache[row + 1][lastColumn],
                                    cache[row + 1][lastColumn - 1]);
                    continue;
                }

                cache[row][column] = matrix[row][column] +
                        Math.min(cache[row + 1][column],
                                Math.min(cache[row + 1][column + 1],
                                        cache[row + 1][column - 1]));
            }
        }

        int min = Integer.MAX_VALUE;
        for (int i : cache[0]) {
            min = Math.min(i, min);
        }

        return min;
    }
}

[labuladong]

@guqihao-7 @aizigao 加油💪🏻

[yangji78]

C++

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int n = matrix.size();
        if (n == 1) return matrix[0][0];
        vector<vector<int>> dp(n + 1, vector<int>(n + 1));
        int res = INT_MAX;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (j == 1)
                    dp[i][j] = matrix[i - 1][j - 1]  +
                            min(dp[i - 1][j], dp[i - 1][j + 1]);
                else if (j == n)
                    dp[i][j] = matrix[i - 1][j - 1]  +
                            min(dp[i - 1][j - 1], dp[i - 1][j]);
                else
                    dp[i][j] = matrix[i - 1][j - 1]  +
                            minVal(dp[i - 1][j - 1], dp[i - 1][j], dp[i - 1][j + 1]);
                if (i == n) res = min(res, dp[i][j]);
            }
        }
        return res;
    }
    int minVal(int i, int j, int k) {
        return min(i, min(j, k));
    }
};

[karta88821]

C++ 加了一些說明

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int n = matrix.size();

        // 建立一個跟原本matrix一樣大小的dp table
        // 每一格設定為 pathsum的最大值+1 -> 10001 = 100(n) * 100(matrix[i][j]的最大值為100) + 1
        vector<vector<int>> dp(n, vector<int>(n, 10001)); 

        // Base case
        // 第一個row設定為原本matrix的第一個row
        for (int j=0; j<n; j++) dp[0][j] = matrix[0][j];

        // 從第二個row開始到最後一個row，取matrix[i][j]加上左上、右上和正上方的pathsum的「最小值」
        for (int i=1; i<n; i++) {
            for (int j=0; j<n; j++) {
                int curr = matrix[i][j];
                if (j-1 >= 0) dp[i][j] = min(dp[i][j], dp[i-1][j-1] + curr); // left top
                if (j+1 < n)  dp[i][j] = min(dp[i][j], dp[i-1][j+1] + curr); // right top
                dp[i][j] = min(dp[i][j], dp[i-1][j] + curr);                 // top
            }
        }

        // dp table的最後一個row的最小值即為min falling path sum
        int res = INT_MAX;

        for (int j=0; j<n; j++) {
            if (dp[n-1][j] < res)
                res = dp[n-1][j];
        }

        return res;
    }
};

[jaqueline-lu]

可能是stupid question。我根据你的逻辑写了python的code，不知道为什么中间列最后一行总是会被算前一列的结果影响，导致算不出来正确的答案：

class Solution:

    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        n = len(matrix)
        memo = [[67890]*n]*n

        res = float('inf')

        def dp(matrix,i,j):
            print(i,j)
                # check validation
            if i >= len(matrix) or j >= len(matrix[0]) or i < 0 or j < 0:
                return 98765

                # base case
            if i == 0:

                return matrix[0][j]

                # if appear in memo
            if memo[i][j] != 67890:
                return memo[i][j]

            # print(matrix[i][j],dp(matrix,i-1,j),dp(matrix,i-1,j-1),dp(matrix,i-1,j+1))
            memo[i][j] = matrix[i][j] + min(dp(matrix,i-1,j-1),dp(matrix,i-1,j),dp(matrix,i-1,j+1))

            return memo[i][j]

        # falling to any one of the bottom
        for j in range(n):
            res = min(res,dp(matrix,n-1,j))

        return res

[Velliy]

@xiaoxu-git 个人感觉正确步骤是先找到方程式然后定义dp，然后才知道base case是啥。

[Velliy]

@xiaoxu-git 前面说错了，是先定义dp，然后推导方程式，然后才知道base case咋定义。

[zzjzz9266a]

贴一个省空间的解法

var minFallingPathSum = function(matrix) {
  const length = matrix.length;

  if (length == 1) return matrix[0][0];

  let res = Infinity;
  for (let i = 1; i < length; i ++) {
    for (let j = 0; j < length; j ++) {
      if (j == 0) {
        matrix[i][j] = matrix[i][j] + Math.min(matrix[i - 1][j], matrix[i - 1][j + 1]);
      }else if (j == length - 1) {
        matrix[i][j] = matrix[i][j] + Math.min(matrix[i - 1][j], matrix[i - 1][j - 1]);
      }else {
        matrix[i][j] = matrix[i][j] + Math.min(matrix[i - 1][j], matrix[i - 1][j - 1], matrix[i - 1][j + 1]);
      }
      if (i == length - 1) res = Math.min(res, matrix[i][j]);
    }
  }
  return res;
};

[Nelsonlin0321]

Python 选手： 自低向上

class Solution:
    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        n = len(matrix)

        row = [None for _ in range(n)]
        dp = [row.copy() for _ in range(n)]

        # definition
        #dp[i][j]: the distance from i,j to top

        # base case
        dp[0] = matrix[0]

        for row in range(1,n):
            for col in range(n):

                # (row + 1, col - 1)
                left_val = float('inf')
                if 0<=row - 1<n and 0<=col + 1<n:
                    left_val = dp[row - 1][col + 1]

                # (row + 1, col)
                right_val = float('inf')
                if 0<=row-1<n:
                    down_val = dp[row - 1][col]

                # (row + 1, col + 1)
                right_val = float('inf')
                if 0<=row - 1<n and 0<=col - 1<n:
                    right_val  = dp[row - 1][col - 1]

                dp[row][col] = min([left_val,down_val,right_val])+ + matrix[row][col]

        return min(dp[-1])

[SerenaZZZZZ]

从上到下找遍历每一个数字，找这个数字分别加上一行三个数字的最小值，存在这个数字的位置，直到最后一行返回最后一行的最小数字 2 ms, faster than 94.69% 42.6 MB, less than 98.23%

class Solution {
    public int minFallingPathSum(int[][] matrix) {
        if (matrix==null || matrix.length==0) return 0;
        int m = matrix.length; int n = matrix[0].length;
        int[][] sum = matrix.clone();
        int res = Integer.MAX_VALUE;
        for (int i=0; i<m; i++){
            for (int j=0; j<n; j++){
                if (i!=0){
                    int min = Integer.MAX_VALUE;
                    for (int k=j-1; k<=j+1; k++){
                        if (k<0 || k==n) continue;
                        min = Math.min(matrix[i-1][k]+sum[i][j],  min);
                    }
                    sum[i][j] = min;
                }
                if (i==m-1) res = Math.min(res, sum[i][j]);
            }
        }
        return res;
    }
}