当前位置：
  1. 首页
  2. 剑指offer刷题第六期
  3. 问题详情

【动态规划专题】LeetCode 64. 最小路径和

本问题对应课程链接：剑指offer刷题第六期

要求：

1、请打卡你的解题代码，如果能简单说一下思路则简单说一下思路。
2、给出你代码所用的时间复杂度和空间复杂度

shuaidi
145 14

共以下 14 个回答

  • kfaebot 普通 2024年5月10日 下午9:39 
    class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m=grid.size();
        int n=grid[0].size();
        int dp[m][n];

        //初始值
        dp[0][0]=grid[0][0];
        for(int i=1;i<m;i++){
            dp[i][0]=grid[i][0]+dp[i-1][0];
        }
        for(int i=1;i<n;i++){
            dp[0][i]=grid[0][i]+dp[0][i-1];
        }

        //关系式
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j]=min(dp[i][j-1],dp[i-1][j])+grid[i][j];
            }
        }
        return dp[m-1][n-1];
    }
};
    0 赞同 0 条回复
  • =.= 普通 2024年4月12日 下午11:05

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

        int[][] dp = new int[m][n];
    dp[0][0] = grid[0][0];
    for(int j=1; j<n; j++){
        dp[0][j] = dp[0][j-1] + grid[0][j];
    }
    for(int i=1; i<m; i++){
        dp[i][0] = dp[i-1][0] + grid[i][0];
    }

    for(int i=1; i<m; i++){
        for(int j=1; j<n; j++){
            dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
        }
    }
    return dp[m-1][n-1];
}

    }

    时间：O(mn)
    空间：O(mn)

    0 赞同 0 条回复
  • 南梁陈庆之 普通 2024年4月8日 下午11:20

    动态规划，找关联关系，结果值和初始值；注意初始值

    class Solution {
    public int minPathSum(int[][] grid) {
        // dp[0][j] = dp[0][j - 1] + grid[0][j]
        // dp[i][0] = dp[i - 1][0] + grid[i][0]
        // dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
        // dp[m - 1][n - 1]

        int m = grid.length, n = grid[0].length;
        int[][] dp = new int[m][n];

        dp[0][0] = grid[0][0];
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for (int i = 1; i < n; i++) {
            dp[0][i] = dp[0][i - 1] + grid[0][i];
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[m - 1][n - 1];

    }
}
    0 赞同 0 条回复
  • 神经蛙 普通 2024年4月2日 下午11:10

    class Solution {
    public:
    int minPathSum(vector<vector>& grid) {
    if (grid.size() 0 || grid[0].size() 0) {
    return 0;
    }
    int rows = grid.size(), columns = grid[0].size();
    auto dp = vector < vector     > (rows, vector (columns));
    dp[0][0] = grid[0][0];
    for (int i = 1; i < rows; i++) {
    dp[i][0] = dp[i – 1][0] + grid[i][0];
    }
    for (int j = 1; j < columns; j++) {
    dp[0][j] = dp[0][j – 1] + grid[0][j];
    }
    for (int i = 1; i < rows; i++) {
    for (int j = 1; j < columns; j++) {
    dp[i][j] = min(dp[i – 1][j], dp[i][j – 1]) + grid[i][j];
    }
    }
    return dp[rows – 1][columns – 1];
    }
    };
    打卡

    0 赞同 0 条回复
  • 白雪公主倒拔垂杨柳 永久会员 2024年4月2日 下午8:33 
        /*动态规划三部曲

    1、定义数组含义
    dp[i][j]:当到达 (i,j) 这个位置时，最小路径和为 dp[i][j]。

    2、关系式
    dp[i][j]. dp[i-1][j] dp[i][j-1]
    如何才能到达 （i，j）
    （1）要么从 （i-1,j) 这个位置向下走一步=>dp[i][j] = dp[i-1][j] + grid[i][j]
    （2）要么是从(i,j-1)这个位置向右走一步=>dp[i][j] = dp[i][j-1] + grid[i][j]

    dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

    3、初始值
    dp[0][0~m-1]
    dp[0~n-1][0]

    */
class Solution {
    public int minPathSum(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        int dp[][] = new int[n][m];

        dp[0][0]=grid[0][0];
        int i,j;
        for(j=1;j<m;j++){
            dp[0][j]=dp[0][j-1]+grid[0][j];
        }
        for(i=1;i<n;i++){
            dp[i][0]=dp[i-1][0]+grid[i][0];
        }

        for(i=1;i<n;i++){
            for(j=1;j<m;j++){
                if(dp[i-1][j]<dp[i][j-1]){
                    dp[i][j]=dp[i-1][j]+grid[i][j];
                }else{
                    dp[i][j]=dp[i][j-1]+grid[i][j];
                }
            }
        }

        return dp[n-1][m-1];
    }
}

    时间复杂度：O（mn）
    空间复杂度：O（mn）

    0 赞同 0 条回复
  • heathhou 普通 2024年4月1日 下午10:16 
    class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        if(m <= 0 || n <= 0){
            return 0;
        }

        // 定义数组元素的含义
        // 当机器人从左上角走到（i, j）这个位置时，最短的路径和是 dp[i] [j]
        vector<vector<int>> dp(grid.size(), vector<int>(grid[0].size(), -1));

        // 找出数组元素之间的关系式
        // dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + gird[i][j]

        // 找出初始值, 根据dp关系式可以知道，需要初始化第一行与第一列
        dp[0][0] = grid[0][0];
        for(int j = 1; j < grid[0].size(); ++j){
            dp[0][j] = dp[0][j-1] + grid[0][j];
        }
        for(int i = 1; i < grid.size(); ++i){
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }

        // 根据dp关系式进行推导
        for(int i = 1; i < grid.size(); ++i){
            for(int j = 1; j < grid[0].size(); ++j){
                dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + grid[i][j];
            }
        }

        return dp[m-1][n-1];
    }
};
    0 赞同 0 条回复
  • 一个达不刘 普通 2024年4月1日 上午11:47

    class Solution {
    public:
    int minPathSum(vector<vector>& grid) {
    //细分边界，一一讨论
    for(int i=0;i<grid.size();i++){
    for(int j=0;j<grid[0].size();j++){
    if(i0&& j0) continue;
    else if(i0) grid[i][j] = grid[i][j-1] + grid[i][j];
    else if(j    0) grid[i][j] = grid[i-1][j] + grid[i][j];
    else grid[i][j] = min(grid[i-1][j],grid[i][j-1]) + grid[i][j];
    }
    }
    return grid[grid.size()-1][grid[0].size()-1];
    }
    };

    0 赞同 0 条回复
  • Jimmy 普通 2024年3月31日 下午10:59

    时间复杂度O(mn)，空间复杂度O(1)

    class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        for(int i=0;i<grid.size();i++)
        {
            for(int j=0;j<grid[0].size();j++)
            {
                if(i == 0 && j == 0) continue;
                else if(i == 0) grid[i][j] = grid[i][j-1] + grid[i][j];
                else if(j == 0) grid[i][j] = grid[i-1][j] + grid[i][j];
                else grid[i][j] = min(grid[i][j-1],grid[i-1][j]) + grid[i][j];
            }
        }
        return grid[grid.size()-1][grid[0].size()-1];
    }
};
    0 赞同 0 条回复
  • 王位詮釋 普通 2024年3月31日 下午5:01 
    没有优化的：
class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;//有多少行
        int n = grid[0].length;//有多少列
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        //初始化
        for(int i=1;i<m;i++){
            dp[i][0]=dp[i-1][0]+grid[i][0];
        }
        for(int i = 1;i<n;i++){
            dp[0][i] = dp[0][i-1]+grid[0][i];
        }
        for(int i=1;i<m;i++){
            for(int j = 1;j<n;j++){
                dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];
            }
        }
        return dp[m-1][n-1];
    }
}
时间复杂度：O(n2)
空间复杂度：O(n2)

优化过的：
class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;//有多少行
        int n = grid[0].length;//有多少列
        int[] dp = new int[n];//因为要存储每一行算出来的数据，所以要申请n大小的数组
        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] = Math.min(dp[j-1],dp[j])+grid[i][j];
            }
        }
        return dp[n-1];
    }
}
时间复杂度：O(n2)
空间复杂度：O(n)
    0 赞同 0 条回复
  • 机电皮怪 永久会员 2024年3月31日 上午11:30

    两个版本：

    “`C++
    class Solution {
    public:
    int minPathSum(vector>& grid) {
    int m = grid.size();
    int n = grid[0].size();
    vector> dp(m, vector(n, 0) );

        dp[0][0] = grid[0][0];
    for(int i = 1; i < m; i++)
    {
        dp[i][0] = dp[i - 1][0] + grid[i][0];
    }
    for(int i = 1; i < n; i++)
    {
        dp[0][i] = dp[0][i - 1] + grid[0][i];
    }
    //关系式:dp[i][j] = min(dp[i-1][j] + grid[i][j], dp[i][j-1] + grid[i][j])
    for(int i = 1; i < m; i++)
    {
        for(int j = 1; j < n; j++)
        {
            dp[i][j] = min(dp[i - 1][j] + grid[i][j], dp[i][j - 1] + grid[i][j]);
        }
    }
    return dp[m - 1][n - 1];
}

    };
    /******************************************************************/
    class Solution {
    public:
    int minPathSum(vector<vector>& grid) {
    for(int i = 0; i < grid.size(); i++)
    {
    for(int j = 0; j < grid[0].size(); j++)
    {
    if(i 0 && j 0)
    {
    continue;
    }
    else if(i 0)
    {
    grid[i][j] = grid[i][j – 1] + grid[i][j];
    }
    else if(j     0)
    {
    grid[i][j] = grid[i – 1][j] + grid[i][j];
    }
    else
    {
    grid[i][j] = min(grid[i – 1][j], grid[i][j – 1]) + grid[i][j];
    }
    }
    }
    return grid[grid.size() – 1][grid[0].size() – 1];
    }
    };

    “`

    0 赞同 0 条回复
  • Thaddeus 永久会员 2024年3月31日 上午9:19

    打卡

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

        for(int i = 1; i < m; ++i) {
            for(int j = 0; j < n; ++j) {
                if(j == 0) dp[j] = dp[j] + grid[i][j];
                else dp[j] = min(dp[j], dp[j - 1]) + grid[i][j]; 
            }
        }
        return dp[n - 1];
    }
};
    0 赞同 0 条回复
  • 方铎码农 普通 2024年3月30日 下午10:01 
    //O(mn)复杂度还是太高了
class Solution {
    public int minPathSum(int[][] grid) {
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[0].length; j++){
                if(i == 0 && j == 0) continue;
                else if(i == 0) grid[i][j] = grid[i][j-1] + grid[i][j];
                else if(j == 0) grid[i][j] = grid[i-1][j] + grid[i][j];
                else grid[i][j] = Math.min(grid[i-1][j],grid[i][j-1])+grid[i][j];
            }
        }
        return grid[grid.length - 1][grid[0].length - 1];
    }
}

    时间复杂度$O(mn)$，空间复杂度因为用原来数组为O(1)，但是还是太慢

    0 赞同 0 条回复
  • 紫芝 普通 2024年3月30日 下午4:24

    时间复杂度：O(mn)
    空间复杂度：O(n)

    “`c++
    class Solution {
    public:
    int minPathSum(vector>& grid) {
    int row = grid.size(), col = grid[0].size();
    vector dp(col, 0);
    dp[0] = grid[0][0];
    for (int j=1; j

    0 赞同 0 条回复
  • 云无深雁影 普通 2024年3月29日 下午11:39

    class Solution {
    public int minPathSum(int[][] grid) {
    for(int i = 0; i < grid.length; i++)
    for(int j = 0; j < grid[0].length; j++){
    if(i 0 && j 0)
    continue;
    else if(i 0)
    grid[i][j] = grid[i][j-1] + grid[i][j];
    else if(j     0)
    grid[i][j] = grid[i-1][j] + grid[i][j];
    else
    grid[i][j] = Math.min(grid[i-1][j],grid[i][j-1]) + grid[i][j];
    }
    return grid[grid.length-1][grid[0].length-1];
    }
    }
    //时间复杂度O(nm)
    //空间复杂度O(1)

    0 赞同 0 条回复

# 回答此问题

后才能回答