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

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

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

要求：

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

shuaidi
186 10

共以下 10 个回答

  • hi 普通 2023年11月10日 下午9:54
    1. 首先得到的递推数组是 f[i][j] = min(f[i – 1][j] + grid[i][j] , f[i][j – 1] + grid[i][j])
    2. 但数组中是[0][0]/[0][i]/[i][0]直接进入循环会有边界问题[-1]
    3. 它不能直接进入循环，需要用判断语句，且把方程分开写求最小值
    4. 去掉状态转移方程里的i 把二维压缩为一维
    class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        vector<vector<int>> f(n, vector<int>(m, INT_MAX));
        grid[0].size();

        for(int i = 0; i <= n - 1; i++)
            for(int j = 0; j <= m - 1; j++)
                if(!i && !j) f[i][j] = grid[i][j];
                else{
                    if(i) f[i][j] = min(f[i][j], f[i-1][j] + grid[i][j]);
                    if(j) f[i][j] = min(f[i][j], f[i][j-1] + grid[i][j]);
                }

        return f[n - 1][m - 1];       
    }
};
    0 赞同 0 条回复
  • June 普通 2023年10月9日 下午9:00 
    class Solution {
    public int minPathSum(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        int[] dp = new int[col]; // 压缩成一维
        dp[0] = grid[0][0];
        for(int i=1;i < col ; i++)
            dp[i] = grid[0][i] + dp[i-1];

        for(int i=1 ; i < row ; i++ ) {
            for(int j=0; j < col ;j++) {
                if(j!=0)
                    dp[j] = Math.min(dp[j - 1]+grid[i][j] , dp[j] + grid[i][j]);
                else
                    dp[j] = dp[j] + grid[i][j];
            }
        }
        return dp[col-1];
    }
}
    0 赞同 0 条回复
  • Marshan 普通 2023年8月28日 下午9:08 
    class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        // dp[i] 表示从左上角到该位置的最小路径和
        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] += grid[i][0];
            for(int j = 1;j < n;++j){
                dp[j] = min(dp[j-1],dp[j]) + grid[i][j];
            }
            // for(int num:dp){
            //     cout<<num<<" ";
            // }
            // cout<<endl;
        }

        return dp[n-1];
    }
};
    0 赞同 0 条回复
  • mpweixin用户 普通 2023年8月21日 上午11:05 
    class Solution {
    public int minPathSum(int[][] grid) {

        //[1,3,1],  [1,4,5]  111
        //[1,5,1],->[2,7,6]  200
        //[4,2,1]   [6,8,7]  600
        // 和上一题异曲同工之妙 可以用递归但是超时 转而用动态规划
        // 自己ac的 牛逼
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        int sumX = 0;
        for (int i = 0; i < m; i++) {
            sumX += grid[i][0];
            dp[i][0] = sumX;
        }
        int sumY = 0;
        for (int i = 0; i < n; i++) {
            sumY += grid[0][i];
            dp[0][i] = sumY;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                // 找到dp递推公式 自己这个点的值加上上面的和左边的最小值，就是到达这个点和的最小值呀
                dp[i][j] = grid[i][j] + Math.min(dp[i-1][j], dp[i][j-1]);
            }
        }
        return dp[m-1][n-1];
    }
}
    0 赞同 0 条回复
  • Mby 普通 2023年8月14日 下午6:58 
    class Solution {
    public int minPathSum(int[][] grid) {
        int[] dp = new int[grid[0].length];
        for(int i = grid.length - 1;i >= 0; i--){
            for(int j = grid[0].length - 1; j >= 0; j--){
                if(i == grid.length - 1 && j != grid[0].length - 1)
                    dp[j] = grid[i][j] + dp[j + 1];
                else if(j == grid[0].length - 1 && i != grid.length - 1)
                    dp[j] = grid[i][j] + dp[j];
                else if(j != grid[0].length - 1 && i != grid.length - 1)
                    dp[j] = grid[i][j] + Math.min(dp[j], dp[j + 1]);
                else
                    dp[j] = grid[i][j];

            }
        }
        return dp[0];
        //时间复杂度：O(mn)
        //空间复杂度：O(mn)
    }
}
    0 赞同 0 条回复
  • 北辰 普通 2023年8月14日 上午10:20 
    class Solution {
    public int minPathSum(int[][] grid) {
        int[][] dp = new int[grid.length][grid[0].length];
        dp[0][0] = grid[0][0];
        for(int i=1;i<grid[0].length;i++) {
            dp[0][i] = grid[0][i]+dp[0][i-1];
        }
        for(int i=1;i<grid.length;i++) {
            dp[i][0] = grid[i][0]+dp[i-1][0];
        }
        for(int i=1;i<grid.length;i++) {
            for(int j=1;j<grid[0].length;j++) {
                dp[i][j] = grid[i][j]+Math.min(dp[i-1][j],dp[i][j-1]);
            }
        }
        return dp[grid.length-1][grid[0].length-1];
    }
}

    时间复杂度：O（mn）

    0 赞同 0 条回复
  • NullPointerException 普通 2023年8月8日 下午12:00

    class Solution {
    public int minPathSum(int[][] grid) {
    //只能向下 或着右走 那么代表目前元素只能 通过由上面或者左边
    int dp[][]=new int [grid.length+1][grid[0].length+1];
    for(int i=0;i<dp.length;i++)
    {
    dp[i][0]=2001;
    }
    for(int i=0;i<dp[0].length;i++)
    {
    dp[0][i]=2001;
    }
    dp[1][1]=grid[0][0];
    for(int i=1;i<dp.length;i++)
    {
    for(int j = 1;j<dp[0].length;j++)
    {
    if(i1&&j1)
    {
    continue;
    }
    dp[i][j]=Math.min(dp[i-1][j]+grid[i-1][j-1],dp[i][j-1]+grid[i-1][j-1]);
    }
    }
    return dp[dp.length-1][dp[0].length-1];
    }
    }

    0 赞同 0 条回复
  • AD钙奶 普通 2023年8月7日 上午11:43

    dp[i][j] 从0 0 到 i j的路径和

    class Solution {
    public int minPathSum(int[][] grid) {
        int[][] dp = new int[grid.length][grid[0].length];
        dp[0][0] = grid[0][0];
        for(int i = 1; i < grid.length; i ++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0]; 
        }
        for(int i = 1; i < grid[0].length; i ++) {
            dp[0][i] = dp[0][i - 1] + grid[0][i]; 
        }

        for(int i = 1; i < grid.length; i ++) {
            for(int j = 1; j < grid[0].length; j ++) {
                dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
            }
        }
        return dp[grid.length - 1][grid[0].length - 1];
    }
}
    0 赞同 0 条回复
  • 长河呼叫黄江 普通 2023年8月5日 下午4:31

    8.5
    Day26：下面是代码

    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];
                else if(j == 0) grid[i][j] += grid[i - 1][j];
                else grid[i][j] += Math.min(grid[i][j - 1], grid[i - 1][j]);
            }
        }
        return grid[grid.length - 1][grid[0].length - 1];
    }
}
    0 赞同 0 条回复
  • 阿尚 普通 2023年8月5日 下午2:09 
    //二维dp
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 j = 1; j < n; j++){
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }

        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 条回复

# 回答此问题

后才能回答