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

[utterances-bot]

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

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

[xiaoxu-git]

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

[morganwu277]

base case 有时候 和 dp函数是兼容的，有时候并不兼容。
这个例子里，恰好就是兼容的：从第一行到当前点的最短path sum。
所以本例中 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;
    }

[fly-han]

从上往下落，确实好理解一些。尤其是能对应文中的这句话，【从第一行（matrix[0][..]）向下落，落到位置 matrix[i][j] 的最小路径和为 dp(matrix, i, j)。】
东哥的方法从下往上，和这句话是反着的。

[fly-han]

仔细又想了下，这种方式，因为baseCase有问题，所以无法取得正确的结果

[HCWGH]

这个有问题吧，你的的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]由下层推到得到，明显不对，你既然想自底向上那就别用递归函数，用迭代。

[HCWGH]

public int minFallingPathSum(int[][] matrix) {
    int n = matrix.length;
    int[][] 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));
        for (int j = 0; j < matrix[i].length; j++) {
            //base case
            if (i == 0) {
                dp[i + 1][j + 1] = matrix[i][j];
                continue;
            }
            dp[i + 1][j + 1] = matrix[i][j] + Math.min(Math.min(dp[i][j], dp[i][j + 1]), j + 2 >= n + 1 ? Integer.MAX_VALUE : dp[i][j + 2]);
        }
    }
    for (int i = 0; i < dp[n].length; i++) {
        min = Math.min(min, dp[n][i]);
    }
    return min;
}

[HCWGH]

这是我写的迭代自底向上的思路，应该还可以优化，我只写了初版

[Tokics]

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

[labuladong]

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

[exoreray]

我觉得自顶向下更像是dfs加pruning的思维模式，因为有递归在里面。我对dp的理解是只有单纯的对数组遍历就可以解决的算法模式。感觉这样分类定义这两种对我个人来讲更make sense。不知道这样理解有没有问题。

[labuladong]

可以这样理解。但我们一般说 DFS 是「遍历」算法，而动态规划运用到的是「分解问题」的思路，可以看下 二叉树纲领篇 中的总结。

[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;
    }
}

[icecreampat]

可以在matrix两端各加一列最大值，遍历时只遍历[1,n]列，就不用分开考虑了

[HCWGH]

dp数组降为以为数组

public int minFallingPathSum(int[][] matrix) {
    int n = matrix.length;
    int[] dp = new int[n + 2];
    dp[0] = dp[n] = Integer.MAX_VALUE;
    int min = Integer.MAX_VALUE;
    for (int i = 0; i < n; i++) {
        int preVal = Integer.MAX_VALUE;
        for (int j = 0; j < n; j++) {
            //base case
            if (i == 0) {
                dp[j + 1] = matrix[i][j];
            } else {
                int tempVal = dp[j + 1];
                dp[j + 1] = matrix[i][j] + Math.min(Math.min(preVal, dp[j + 1]), dp[j + 2]);
                preVal = tempVal;
            }
            System.out.println(dp[j + 1] + " " + preVal);
            //n==last index,统计结果
            if (i == n - 1) {
                min = Math.min(min, dp[j + 1]);
            }
        }
    }
    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];
    }
};

[stephengineer]

pass matrix as reference.

[labuladong]

@q240627995 C++ 里面递归函数的数组参数要传引用

[1haoshao2]

东哥这一句话让我好多超时的通过了，哈哈哈。

[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));
    }
}

[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;
    }
}

[yonggui-yan]

叮咚！打卡

[lpdswing]

贴一个python

class Solution:
    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        @cache
        def dp(i, j):
            # 检查索引
            nonlocal n
            if i < 0 or j < 0 or i >= n or j >= n:
                return 99999
            # base case
            if i == 0:
                return matrix[0][j]
            return matrix[i][j] + min(dp(i-1, j), dp(i-1, j-1), dp(i-1, j+1))

        n = len(matrix)
        res = inf
        for j in range(n):
            res = min(res, dp(n-1, j))
        return res

[yinmaoning55]

感觉这样写更容易理解，从上往下递归

class Solution {
    int[][] memo;
    public int minFallingPathSum(int[][] matrix) {
        int w = matrix[0].length;
        memo = new int[matrix.length][w];
        for (int i = 0; i < w; i++) {
        Arrays.fill(memo[i], 66666);
        }
        int res = Integer.MAX_VALUE;
        for(int i = 0; i < w;i++){
            res = Math.min(res,dp(matrix,0,i));
        }
        return res;
    }
    public int dp(int[][] matrix, int i, int j){
        if(i > matrix.length - 1) return 0;
        int a = Integer.MAX_VALUE,b = a,c = a;
        i++;
        if(memo[i - 1][j] != 66666){
            return memo[i - 1][j];
        }
        if(j == 0){
            c = dp(matrix,i,j + 1);
        }else if(j == matrix[0].length - 1){
            a = dp(matrix,i,j - 1);
            
        }else{
            a = dp(matrix,i,j - 1);
            c = dp(matrix,i,j + 1);
        }
        b = dp(matrix,i,j);
        memo[i - 1][j] = matrix[i - 1][j] + Math.min(a,Math.min(b,c));
        return memo[i - 1][j];
    }
   
}

[zhaoedf]

自底向上（填满memo的每一项）可能容易理解点呢。

    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        
        row, col = len(matrix), len(matrix[0])
        self.memo = [[102*100]*col for i in range(row)]
        
        
        self.memo[0] = matrix[0]
        for i in range(1, row):
            for j in range(col):
                cut = slice(max(0, j-1), min(j+2, col))
                temp = self.memo[i-1][cut]
                self.memo[i][j] = min(self.memo[i][j], min(temp)+matrix[i][j])
                    
        # print(self.memo)
        return min(self.memo[-1])

[BigBeardYT]

为什么这样写的时间复杂度很高，用的自顶向上的dp方法（难道是因为有两个循环？）
class Solution {
public int minFallingPathSum(int[][] matrix) {
int n = matrix.length;
if(1 == n){
return matrix[0][0];
}
// 定义一个dp数组，dp[i][j]表示（i，j）位的最小下降路径最小和
int [][] dp = new int[n][n];
// 初始化，
for(int i = 0;i < n;i++){
dp[0][i] = matrix[0][i];
}
// 第一行已经全部算过了，直接从第二行开始
for(int row = 1;row < n;row++){
for(int col = 0;col < n;col++){
int a = dp[row-1][col > 0 ? col-1 : col];
int b = dp[row-1][col+1 < n ? col+1 : col];
int c = dp[row-1][col];
dp[row][col] = matrix[row][col] + threeMin(a, b, c);
}
}
int res = Integer.MAX_VALUE;
for(int i = 0;i < n;i++){
res = Math.min(res, dp[n-1][i]);
}
return res;
}
public static int threeMin(int a, int b, int c){
if(a < b){
return a < c ? a : c;
}
else{
return b < c ? b : c;
}
}
}

[CarlLy7]

二刷打卡

[connorwang0901]

改写了一个小学生写法的 非递归版dp写法

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

     for(int i = 0; i < n; i++) {
         for(int j = 0; j < n; j++) {
             if(i < 0 || i >= n || j < 0 || j >= n) continue;
             if(i == 0) {
                 dp[i][j] = matrix[i][j];
                 continue;
             }
            int rightTop = 9999999;
            int top = 9999999;
            int leftTop = 9999999;
            if(i - 1 >= 0 && i - 1 < n && j + 1 >= 0 && j + 1 < n) 
                rightTop = dp[i - 1][j + 1];
            if(i - 1 >= 0 && i - 1 < n && j >= 0 && j < n) 
                top = dp[i - 1][j];
            if(i - 1 >= 0 && i - 1 < n && j - 1 >= 0 && j - 1 < n) 
                leftTop = dp[i - 1][j - 1];
            dp[i][j] = matrix[i][j] + 
                        Math.min(Math.min(rightTop, top), leftTop);
         }
     }

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

     return res;
}

}

[xidianwubo121381]

补一个使用额外空间的方法，代码会看起来简单一些

class Solution(object):
   def minFallingPathSum(self, matrix):
       """
       :type matrix: List[List[int]]
       :rtype: int
       """
       seq_len = len(matrix)
       # 构造一个更大的矩阵，包围原来的矩阵
       dp = [[0 for _ in range(seq_len + 2)] for _ in range(seq_len + 2)]

       # 正常遍历就行
       for i in range(1, seq_len + 1):
           for j in range(1, seq_len + 1):
               # 左边界
               if j == 1:
                   dp[i][j] = min(dp[i-1][j], dp[i-1][j+1]) + matrix[i-1][j-1]
               # 右边界
               elif j == seq_len:
                   dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + matrix[i-1][j-1]
               else:
                   dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]) + matrix[i-1][j-1]

       # 最后一层
       # print(dp)
       return min(dp[seq_len][1:seq_len+1])

[RomeoFourier]

使用dp数组为什么会比递归慢这么多呀？？？一个1ms，一个5ms。按理说都是加了备忘录的

[HCWGH]

有几个疑问：

1.我这里把二维的dp数组降为一维的dp数组，但是在commit的时候，空间复杂度按道理来说应该是O(N)，但是结果却比二维数组的效果差，这是不能理解的
2.我这里是自底向上的迭代解法，时间复杂度也是O(N^2)但是效果还是比递归的O(N^2)差。这是咋回事，测试用例的问题吗？

class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;
        int[] dp = new int[n + 2];
        dp[0] = dp[n + 1] = Integer.MAX_VALUE;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int preVal = dp[0];
            for (int j = 0; j < n; j++) {
                //base case
                if (i == 0) {
                    dp[j + 1] = matrix[i][j];
                } else {
                    int tempVal = dp[j + 1];
                    dp[j + 1] = matrix[i][j] + Math.min(Math.min(preVal, dp[j + 1]), dp[j + 2]);
                    preVal = tempVal;
                }
                //n==last index,统计结果
                if (i == n - 1) {
                    min = Math.min(min, dp[j + 1]);
                }
            }
        }
        return min;
    }
}

[yuanshuli11]

66666 99999 这些用 math.MaxInt32 代替就可以了吧？（golang）
突然来一个66666 99999 增加了理解成本