最小路径和 （ LeetCode 64 ）

一、题目描述

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

二、题目解析

三、参考代码

1、Java 代码

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

        // m 表示有多少行
        int m = grid.length;

        // n 表示每一行有多少个元素，即 n 表示有多少列
        int n = grid[0].length;

        // 设置二维数组 dp 用来储存每个位置的最优解
        // dp[0][0] 表示第 0 行第 0 列的最优解
        // dp[0][i] 表示第 0 行第 i 列的最优解
        // dp[j][0] 表示第 j 行第 0 列的最优解
        // dp[i][j] 表示第 i 行第 j 列的最优解
        int[][] dp = new int[m][n];

        // 初始化 dp[0][0]，由于只有一个元素
        // 所以 dp[0][0] 的最优解就是 grid[0][0] 这个元素
        dp[0][0] = grid[0][0];

        // i 从 1 遍历到 n - 1 
        // 获取第 0 行中第 i 列的最优解
        // 比如 grid[0] 为 [1,3,2...]
        // 由于每次只能向下或者向右移动一步，此时只能向右移动一步
        // 那么 dp[0][i] 依次为 [1,4,6...]
        for(int i = 1; i < n ; i++){
            // 所以对于只有一行的情况，当前位置的最优解等于前一列的最优解加上该列的值
            dp[0][i] = dp[0][i-1] + grid[0][i];
        }

        // i 从 1 遍历到 n - 1 
        // 获取第 i 行中第 0 列的最优解
        // 比如 grid 为 
        // [1,1,2.......]
        // [5,2,2.......]
        // [2,3,4.......]
        // [..,..,..,...]
        // 由于每次只能向下或者向右移动一步，此时只能向下移动一步
        // 那么 dp[i][0] 就是
        // [1,..........]
        // [6,..........]
        // [7,..........]
        // [............]
        for(int i = 1; i < m ;i++){
            // 所以对于只有一列的情况，当前位置的最优解等于前一行的最优解加上该行的值
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }

        // 接下来从第 1 行到第 m - 1 行
        // 从第 1 列到底 n - 1 列
        // 填充二维数组 dp 里面的值
        // dp[i][j] 表示第 i 行第 j 列的最优解
        for(int i = 1 ; i < m;i++){
            for(int j = 1;j < n;j++){
                // 由于每次只能向下或者向右移动一步
                // 位置 (i,j) 的最优解
                // 等于当前位置上方位置(i-1,j)的最优解和左侧位置(i,j-1)的最优解的较小值
                // 再加上当前位置的值
                dp[i][j] =  Math.min(dp[i-1][j],dp[i][j-1]) + grid[i][j] ;
            }
        }

        // dp[m-1][n-1] 表示第 m - 1 行第 n - 1 列的最优解
        // 返回这个结果即可
        return dp[m-1][n-1];
    }
}

2、C++ 代码

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        // m 表示有多少行
        int m = grid.size();

        // n 表示每一行有多少个元素，即 n 表示有多少列
        int n = grid[0].size();

        // 设置二维数组 dp 用来储存每个位置的最优解
        // dp[0][0] 表示第 0 行第 0 列的最优解
        // dp[0][i] 表示第 0 行第 i 列的最优解
        // dp[j][0] 表示第 j 行第 0 列的最优解
        // dp[i][j] 表示第 i 行第 j 列的最优解
        auto dp = vector < vector <int> > (m, vector <int> (n));

        // 初始化 dp[0][0]，由于只有一个元素
        // 所以 dp[0][0] 的最优解就是 grid[0][0] 这个元素
        dp[0][0] = grid[0][0];

        // i 从 1 遍历到 n - 1 
        // 获取第 0 行中第 i 列的最优解
        // 比如 grid[0] 为 [1,3,2...]
        // 由于每次只能向下或者向右移动一步，此时只能向右移动一步
        // 那么 dp[0][i] 依次为 [1,4,6...]
        for(int i = 1; i < n ; i++){
            // 所以对于只有一行的情况，当前位置的最优解等于前一列的最优解加上该列的值
            dp[0][i] = dp[0][i-1] + grid[0][i];
        }

        // i 从 1 遍历到 n - 1 
        // 获取第 i 行中第 0 列的最优解
        // 比如 grid 为 
        // [1,1,2.......]
        // [5,2,2.......]
        // [2,3,4.......]
        // [..,..,..,...]
        // 由于每次只能向下或者向右移动一步，此时只能向下移动一步
        // 那么 dp[i][0] 就是
        // [1,..........]
        // [6,..........]
        // [7,..........]
        // [............]
        for(int i = 1; i < m ;i++){
            // 所以对于只有一列的情况，当前位置的最优解等于前一行的最优解加上该行的值
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }

        // 接下来从第 1 行到第 m - 1 行
        // 从第 1 列到底 n - 1 列
        // 填充二维数组 dp 里面的值
        // dp[i][j] 表示第 i 行第 j 列的最优解
        for(int i = 1 ; i < m;i++){
            for(int j = 1;j < n;j++){
                // 由于每次只能向下或者向右移动一步
                // 位置 (i,j) 的最优解
                // 等于当前位置上方位置(i-1,j)的最优解和左侧位置(i,j-1)的最优解的较小值
                // 再加上当前位置的值
                dp[i][j] =  min(dp[i-1][j],dp[i][j-1]) + grid[i][j] ;
            }
        }

        // dp[m-1][n-1] 表示第 m - 1 行第 n - 1 列的最优解
        // 返回这个结果即可
        return dp[m-1][n-1];
    }
};

3、Python 代码

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        # m 表示有多少行
       m = len(grid)

       # n 表示每一行有多少个元素，即 n 表示有多少列
       n = len(grid[0])

       # 设置二维数组 dp 用来储存每个位置的最优解
       # dp[0][0] 表示第 0 行第 0 列的最优解
       # dp[0][i] 表示第 0 行第 i 列的最优解
       # dp[j][0] 表示第 j 行第 0 列的最优解
       # dp[i][j] 表示第 i 行第 j 列的最优解
       dp = [[0] * n for _ in range(m)]

       # 初始化 dp[0][0]，由于只有一个元素
       # 所以 dp[0][0] 的最优解就是 grid[0][0] 这个元素
       dp[0][0] = grid[0][0]

       # i 从 1 遍历到 n - 1 
       # 获取第 0 行中第 i 列的最优解
       # 比如 grid[0] 为 [1,3,2...]
       # 由于每次只能向下或者向右移动一步，此时只能向右移动一步
       # 那么 dp[0][i] 依次为 [1,4,6...]
       for i in range( 1 , n ): 
           # 所以对于只有一行的情况，当前位置的最优解等于前一列的最优解加上该列的值
           dp[0][i] = dp[0][i-1] + grid[0][i]


       # i 从 1 遍历到 n - 1 
       # 获取第 i 行中第 0 列的最优解
       # 比如 grid 为 
       # [1,1,2.......]
       # [5,2,2.......]
       # [2,3,4.......]
       # [..,..,..,...]
       # 由于每次只能向下或者向右移动一步，此时只能向下移动一步
       # 那么 dp[i][0] 就是
       # [1,..........]
       # [6,..........]
       # [7,..........]
       # [............]
       for i in range( 1 , m ): 
           # 所以对于只有一列的情况，当前位置的最优解等于前一行的最优解加上该行的值
           dp[i][0] = dp[i-1][0] + grid[i][0]


       # 接下来从第 1 行到第 m - 1 行
       # 从第 1 列到底 n - 1 列
       # 填充二维数组 dp 里面的值
       # dp[i][j] 表示第 i 行第 j 列的最优解
       for i in range(1, m):
            for j in range(1, n):
               # 由于每次只能向下或者向右移动一步
               # 位置 (i,j) 的最优解
               # 等于当前位置上方位置(i-1,j)的最优解和左侧位置(i,j-1)的最优解的较小值
               # 再加上当前位置的值
               dp[i][j] =  min(dp[i-1][j],dp[i][j-1]) + grid[i][j] 

       # dp[m-1][n-1] 表示第 m - 1 行第 n - 1 列的最优解
       # 返回这个结果即可
       return dp[m-1][n-1]

四、动画理解（没有声音）

程序员吴师兄算法训练营永久会员

打赏 收藏 海报 链接