动态规划之最小路径和 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：动态规划之最小路径和

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

[ShermanQ]

前文 动态规划的降维打击：状态压缩 说过降低 dp 数组的技巧，这里也是适用的，不过略微复杂些

本题状态压缩可以直接去掉第一维
（大佬状态压缩那一节讲的太透彻了，醍醐灌顶了属于是）

文中解法状态压缩之后代码如下：

    public int minPathSum2(int[][] grid) {
        int[] dp = new int[grid[0].length];
        dp[0] = grid[0][0];
        for (int  i = 0;i<grid.length;i++){
            for (int j =0;j<dp.length;j++){
                if (i==0 && j==0){
                    continue;
                }
                if (i-1==-1){
                    dp[j] = dp[j-1]+grid[i][j];
                    continue;
                }else if (j-1==-1){
                    dp[j] = dp[j]+grid[i][j];
                    continue;
                }
                dp[j] = Math.min(dp[j],dp[j-1])+grid[i][j];
            }
        }
        return dp[dp.length-1];
    }

[restart365]

好家伙，我硬是没看出来优化前后的区别

[morganwu277]

因为他粘贴错了代码 lol

[Horn1998]

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int row = grid.size(), col = grid[0].size();
        vector<int> dp(col);
        dp[0] = grid[0][0];
        for(int j = 1; j<col; ++j) dp[j] = dp[j-1] + grid[0][j];
        for(int i = 1; i<row; ++i){
            dp[0] = grid[i][0] + dp[0];
            for(int j = 1; j<col; ++j){
                dp[j] = grid[i][j] + min(dp[j], dp[j-1]);
            }
        }
        return dp[col-1];
    }
};

[ginward]

也可以用Dijkstra算法求解：

from queue import PriorityQueue
class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        sol = [ [0] * len(grid[0]) for _ in grid  ]
        visited = set()
        queue = PriorityQueue()
        queue.put( (grid[0][0], (0, 0)) )
        sol[0][0] = grid[0][0]
        while not queue.empty():
            val, node = queue.get()          
            if node in visited:
                continue
            visited.add(node)
            sol[node[0]][node[1]] = val
            if node[0]+1<len(grid):
                down = (node[0]+1, node[1])
                queue.put( (grid[down[0]][down[1]] + val, down) )
            if node[1]+1<len(grid[0]):
                right = (node[0], node[1]+1)
                queue.put( ( grid[right[0]][right[1]] + val, right) )            
        return sol[-1][-1]

[Yjppj]

这是第一道靠自己的能力写出来的，多亏了东哥之前的解决，从之前的一道也看不懂，到后来的看了半天才能看懂，再到今天第一次自己写出来。感觉算法确实很难，但是也能从中获得乐趣。

有一个问题是，东哥后面的好多题目都是通过dptable写出来的，当我自己尝试通过dp函数写的时候，我发现我无法写出，dptable好像比dp函数要容易一些。也可能是我自己的功夫不到家，希望东哥可以多用dp函数解答题目。

[Yjppj]

还有一个问题是：评论之后，就无法再次编辑修改评论

[Yjppj]

Math.min(
dp(grid, i - 1, j)+ grid[i][j],
dp(grid, i, j - 1)+ grid[i][j]
) ;
这个为什么会报错的？感觉这个不是和
Math.min(
dp(grid, i - 1, j),
dp(grid, i, j - 1)
) + grid[i][j];
等价吗？

[labuladong]

@Yjppj 评论之前可以预览，想清楚再评论。你提出的这两种写法，现在看是等价的，但如果放到 for 循环里面，不见得相同，要根据具体情况来看。

[clearlovel7]

python版 DPtable 状态压缩

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m,n=len(grid),len(grid[0])
        dp=[-1 for j in range(n)]
        # base case 相当于dp[0][j]=sum(grid[0][0...j-1])
        dp[0]=grid[0][0]
        for j in range(1,n):
            dp[j]=dp[j-1]+grid[0][j]

        for i in range(1,m):
            # base case  相当于dp[i][0]=sum(grid[0...i-1][0])
            dp[0]+=grid[i][0]
            for j in range(1,n):
                dp[j]=min(dp[j],dp[j-1])+grid[i][j]
        return dp[n-1]

原二维：

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m,n=len(grid),len(grid[0])
        dp=[[-1 for j in range(n)] for i in range(m)]
        dp[0][0]=grid[0][0]
        for j in range(1,n):
            dp[0][j]=dp[0][j-1]+grid[0][j]
        for i in range(1,m):
            dp[i][0]=dp[i-1][0]+grid[i][0]
        for i in range(1,m):
            for j in range(1,n):
                dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]
        return dp[m-1][n-1]

[Maschinist-LZY]

状态压缩思路

每次只存上一行的dp值

Code

C++

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<int> dp(n,0);
        dp[0] = grid[0][0];
        for(int i=1; i<n; i++)dp[i] = dp[i-1] + grid[0][i];
        for(int i=1; i<m; i++){
            dp[0] = dp[0] + grid[i][0];
            for(int j=1; j<n; j++){
                dp[j] = grid[i][j] + min(dp[j], dp[j-1]);
            }
        }
        return dp[n-1];
    }
};

[ZHANG-SHI-CHANG]

大佬，返回最小路径和的所有路径有啥思路呀

[cold-runner]

状态更新时将状态记录下来就可以了吧

[dreamer2q]

JavaScript

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function (grid) {
  let dp = new Array(grid[0].length);

  dp[0] = grid[0][0];
  for (let i = 1; i < dp.length; i++) {
    dp[i] = dp[i - 1] + grid[0][i];
  }

  for (let row = 1; row < grid.length; row++) {
    dp[0] += grid[row][0];
    for (let j = 1; j < grid[0].length; j++) {
      dp[j] = grid[row][j] + Math.min(dp[j - 1], dp[j]);
    }
  }

  return dp[dp.length - 1];
};

[hwhaocool]

因为备忘录和 grid 是一样大的，且由于前进方向是向右、向下，和我们的默认遍历方向一致，所以感觉可以 原地修改，直接把 grid 当成 备忘录来使用

public int minPathSum(int[][] grid) {

        for (int i = 0; i < grid.length; i++) {

            for (int j = 0; j < grid[i].length; j++) {

                int curVal = grid[i][j];

                if (i == 0 && j == 0) {
                    grid[i][j] = curVal;
                } else if(i == 0) {
                    // 左边+当前
                    grid[i][j] = grid[i][j-1] + curVal;
                } else if(j == 0) {
                    // 上面+当前
                    grid[i][j] = grid[i-1][j] + curVal;
                } else {
                    grid[i][j] = Math.min(grid[i][j-1], grid[i-1][j]) + curVal;
                }

            }
        }

        return grid[grid.length-1][grid[0].length-1];
    }

空间复杂度，因为只使用了三个变量，为 O(1)

[guai-shou]

Java版本 压缩空间写法 Dijkstra 算法也可以写这题。算法真的太厉害啦。

    /* 迭代压缩空间写法 */
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        // base case
        dp[0] = grid[0][0];

        // dp
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 第一行第一列。跳过，因为在base case 已经赋值
                if (i == 0 && j == 0) continue;
                // 非第一行的第一列，都只能从上面走到当前位置
                if (j == 0) {
                    dp[j] = dp[j] + grid[i][j];
                }else {
                // 非第一行非第一列，可以从上面或者左边走到当前位置，取最小值
                    dp[j] = Math.min(dp[j - 1], dp[j]) + grid[i][j];
                }
            }
        }
        return dp[n - 1];
    }

[bert82503]

楼主，本题自底向上的 dp 数组的迭代解法未更新到插件里。

[zhongweiLeex]

不知道为啥， 感觉降维这块 对于我来说老费劲了，搞了好几次，还是差点意思，哈哈哈哈。但是那篇降维文章还是很好的， 只是我对于新知识掌握的比较慢，大家加油！

[LebronHarden1]

我也试着压缩了一下,没想到过了哎

class Solution {
    public int minPathSum(int[][] grid) {
        //dp[i][j]可以由dp[i][j-1]和dp[i-1][j]而来
        //那当然是要取上述二者中较小的一个:dp[i][j] = min(dp[i-1][j],dp[i][j-1])
        int m = grid.length;
        int n = grid[0].length;
        int[] dp = new int[n];//因为想返回dp[m-1][n-1],索引哦
        //应当注意边界问题,如:i==0则没有i-1,如:j==0则没有j-1
        dp[0] = grid[0][0];
        //因为第一行只能向右走
        for(int i = 1;i<n;i++){
            dp[i] = dp[i-1]+grid[0][i];
        }
        for(int i = 1;i<m;i++){
            //因为第一行都已经被正确初始化了,所以i在递推公式中已经不会越界了
            for(int j = 0;j<n;j++){
                if(j==0){
                    dp[j] = dp[j]+grid[i][j];
                }else{
                    dp[j]=Math.min(dp[j],dp[j-1])+grid[i][j];
                }
            }
        }
        return dp[n-1];
    }
}

[deepbreath373]

check in

[guqihao-7]

补充一个针对本题解法，也用到了空间压缩，当行数量小于列数量，定义一个长度等于行数量的数组横向滚动填表；当行数量大于列数量时，定义一个长度等于列数量的数组纵向填表
我这里dp定义为[x, y]坐标到右下角的最小值

class Solution {
    public int minPathSum(int[][] grid) {
        lastRow = grid.length - 1;
        lastColumn = grid[0].length - 1;
        if (lastRow < lastColumn) {
            return dp1(grid, 0);
        }
        return dp2(grid, 0);
    }

    int lastRow;
    int lastColumn;

    // 行短
    public int dp1(int[][] grid, int y) {
        int[] dp = new int[lastRow + 1];
        int[] last = grid[lastRow];
        dp[lastRow] = last[lastColumn];
        
        // 初始化
        for (int i = lastRow - 1; i >= 0; i--) {
            dp[i] = dp[i + 1] + grid[i][lastColumn];
        }
        
        for (int i = lastColumn - 1; i >= 0; i--) {
            for (int j = lastRow; j >= 0; j--) {
                if (j == lastRow) {
                    dp[j] = dp[j] + grid[j][i];
                    continue;
                }
                
                dp[j] = Math.min(dp[j], dp[j + 1]) + grid[j][i];
            }
        }
        
        return dp[y];
    }

    // 列短 
    public int dp2(int[][] grid, int y) {
        int[] dp = new int[lastColumn + 1];
        int[] last = grid[lastRow];
        dp[lastColumn] = last[lastColumn];

        // 初始化
        for (int i = lastColumn - 1; i >= 0; i--) {
            dp[i] = grid[lastRow][i] + dp[i + 1];
        }

        for (int i = lastRow - 1; i >= 0; i--) {
            for (int j = lastColumn; j >= 0; j--) {
                if (j == lastColumn) {
                    dp[j] = dp[j] + grid[i][j];
                    continue;
                }

                dp[j] = Math.min(dp[j], dp[j + 1]) + grid[i][j];
            }
        }
        return dp[y];
    }
}

[SUN7700]

东哥，请问对于找工作跳槽而言，写题目时如动态规划，用递归还是迭代去解题好一点？两个的思想都去学习并且每个题目都写出两个方式的解题代码，这样感觉工作量有点大，，，（感觉东哥讲题主要是在使用递归）

[labuladong]

一般来说递归解法更容易理解，迭代解法是递归改出来的。

[SUN7700]

所以东哥，我可以只选其中一个方法去写代码吗😭 每一道题不想把递归还有迭代的代码都写出来，请问应对面试我选哪一个比较好😭

[yonggui-yan]

打卡打卡

"自底向上"

[lucy-xfl]

或许可以考虑贪心

def minPathSum(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        list_research = [0 for _ in range(n)]
        list_research[0] = grid[0][0]

        #first line search
        for i in range(1,n):
            list_research[i] = grid[0][i]+list_research[i-1]

        for j in range(1,m):
            list_research[0] = list_research[0] + grid[j][0]
            for i in range(1,n):
                list_research[i] = min(list_research[i], list_research[i-1])+grid[j][i]
        return list_research[-1]

[bruceeewong]

打卡，终于可以快速按照模板自己写出来二维DP+降维优化了，谢谢东哥的讲解

贴一个降维优化的Java版：

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[] dp = new int[n];  // 一次存一行的min cost
        // base case
        dp[0] = grid[0][0];
        // base case for row 0
        for (int j = 1; j < n; j ++) {
            dp[j] = dp[j-1] + grid[0][j];
        }
        for (int i = 1; i < m; i ++) {
            // 注意列需要从 0 开始，因为每次要更新掉dp[0]
            for (int j = 0; j < n; j ++) {
                if (j - 1 < 0) {
                    dp[j] = dp[j] + grid[i][j];  // 如果j-1越界，即左边没有数，只能选择从上往下走
                } else {
                    dp[j] = Math.min(dp[j], dp[j-1]) + grid[i][j];
                }
            }
        }
        return dp[n-1];
    }
}

[Tal-cat]

Python 解法那里应该是return dp(grid, m-1, n-1)，少了grid~

[EyeDroplyq]

打卡

[shiboys]

阿东的是 dp[i][j] = grid[i][j] + Math.min(dp[i-][j],dp[i][j-1]) 采用的还是如果想要到达二维数组中的一个点，只能是来自左侧或者上面一行。我这里给出按照原题目的要求，一个点可以走到相邻的右边或者下边一个点的视角：就是 memo[i][j] = grid[i][j] + Math.min(dp2(grid, i + 1, j), dp2(grid, i, j + 1)); 的解法：

class Solution {
 public int minPathSum(int[][] grid) {
        memo = new int[grid.length][grid[0].length];
        Arrays.stream(memo).forEach(subArray -> {
            Arrays.fill(subArray, -1);
        });
        return dp(grid, 0, 0);
    }

int dp(int[][] grid, int i, int j) {
        // base case
        // 走到 target node
        if (i == grid.length - 1 && j == grid[0].length - 1) {
            return grid[i][j];
        }
        if (i >= grid.length || j >= grid[0].length) {
            return Integer.MAX_VALUE;
        }

        if (memo[i][j] != -1) {
            return memo[i][j];
        }
        memo[i][j] = grid[i][j] +
                Math.min(dp2(grid, i + 1, j), dp2(grid, i, j + 1));
        return memo[i][j];
    }
}

[shiboys]

dp 函数名应该改为 dp2，主要是为了跟阿东的 dp 函数区别