【动态规划专题】LeetCode 64. 最小路径和-跟着帅地玩副业，开拓第二曲线PlayOffer

Gg 普通 2023年8月5日下午11:33

class Solution {
    // 1、定义dp。2、递推公式 3、初始化 4、确定遍历顺序 5、举例

    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-1][j],grid[i][j-1]); 
                }

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

0 赞同 0 条回复

宁永久会员 2023年3月14日下午12:00

二维数组–>一维数组

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        //min(left, top) + 当前值
        int[] dp = new int[n];
        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++){
            dp[0] = dp[0] + grid[i][0];
            for(int j = 1; j < n; j++){               
                dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
            }
        }
        return dp[n - 1];
    }

    // public int minPathSum(int[][] grid) {
    //     int m = grid.length;
    //     int n = grid[0].length;
    //     //min(left, top) + 当前值
    //     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 条回复

PatNick 普通 2023年1月18日下午5:13

m = len(grid) # 行
    n = len(grid[0]) # 列

    # 定义dp，到达dp[i]表示某一行的i列所在位置的最小路径和
    # 每行动态更新
    dp = [-1] * n
    dp[0] = grid[0][0]
    # 初始化dp
    for _ in range(1,n):
        dp[_] = dp[_-1] + grid[0][_]
    for i in range(1,m):
        for j in range(0,n):
            # 对于第一列的元素dp[0]只能向下走，需要单独计算
            if j == 0:
                dp[j] = dp[j] + grid[i][j]
            else:
                dp[j] = min(dp[j-1],dp[j]) + grid[i][j]

    return dp[-1]

0 赞同 0 条回复

lucca 普通 2023年1月18日下午1:25

DP，类比杨辉三角

时间复杂度 O(MN)
空间复杂度 O(1)

class Solution {
    public int minPathSum(int[][] g) {
        int n = g.length, m = g[0].length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (i == 0 && j == 0) continue;
                if (i == 0) g[i][j] += g[i][j - 1];
                else if (j == 0) g[i][j] += g[i - 1][j];
                else g[i][j] += Math.min(g[i][j - 1], g[i - 1][j]);
            }
        }
        return g[n - 1][m - 1];
    }
}

0 赞同 0 条回复

@ 普通 2022年12月18日上午10:57

时间复杂度：O(N)

空间复杂度：O(1)

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


        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; 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 - 1][j], grid[i][j - 1]);


            }
        }


        return grid[row - 1][col - 1];

    }

    public static void main(String[] args) {
        Solution s = new Solution();
        int[][] ary = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
        int i = s.minPathSum(ary);
        System.out.println(i);
    }
}

0 赞同 0 条回复

Error 普通 2022年12月4日下午10:48

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if i == 0 and j == 0:
                    continue
                elif i == 0 and j !=0:
                    grid[i][j] += grid[i][j - 1]
                elif i != 0 and j == 0:
                    grid[i][j] += grid[i - 1][j]
                else:
                    grid[i][j] += min(grid[i][j - 1], grid[i - 1][j])
        return grid[-1][-1]

时间复杂度 O(n)

0 赞同 0 条回复

🚲南下普通 2022年12月3日下午6:21

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

0 赞同 0 条回复

你有点可爱喔普通 2022年12月3日下午5:26

class Solution {
    public int minPathSum(int[][] grid) {
        ///设 dp 为大小 m \times nm×n 矩阵，其中 dp[i][j]dp[i][j] 的值代表直到走到 (i,j)(i,j) 的最小路径和。
        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];
    }
}

0 赞同 0 条回复

派大星普通 2022年12月2日下午11:15

class Solution {
//时间复杂度O(n)
//空间复杂度O(n)
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }

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

T 普通 2022年11月30日下午8:52

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

0 赞同 0 条回复

y 普通 2022年11月26日下午5:27

var minPathSum = function(grid) {
   let m = grid.length;
   let n = grid[0].length;
   let dp = Array(m).fill(0).map(item => Array(n).fill(0));
   dp[0][0] = grid[0][0];

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

   for (let i = 1; i < m; i++) {
       for (let 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）

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年11月25日下午9:36

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

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 < n;i++){
            dp[0][i] = dp[0][i-1] + grid[0][i];
        }
        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];
    }
}

0 赞同 0 条回复

just 普通 2022年11月24日下午7:52

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

};

0 赞同 0 条回复

訁訁訁訁訁普通 2022年11月24日上午12:22

时间空间O(mn)

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

0 赞同 0 条回复

So 普通 2022年11月23日下午9:35

class Solution {
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int rows = grid.length, columns = grid[0].length;
        int[][] dp = new int[rows][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] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[rows - 1][columns - 1];
    }
}

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

0 赞同 0 条回复

青木普通 2022年11月23日下午9:32

/**
    比较暴力的方法，用一个二维数组保存各个位置上的最小路径，
    由于只能向下或者向右，所以只需要考虑i-1和j-1的情况就可以了

    时间(m*n)
    空间O(m*n)
 */

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

0 赞同 0 条回复

Tolkien 永久会员 2022年11月23日下午3:47

/**
     * 动态规划
     * 时间复杂度：O(mn)
     * 空间复杂度：O(mn)
     * 1. dp数组定义：机器人从(1,1)走到(i,j)的路径所需最小的权重为dp[i][j]
     * 2. 关系式：dp[i][j] = Math.min(dp[i-1][j]+grid[i][j], dp[i][j-1]+grid[i][j])
     * 3. 初始化：dp[i][1] = dp[i-1][1]+grid[i]，dp[1][i] = dp[1][i-1]+grid[1][i]
     */
    public static 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] = 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] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
                }
            }
            return dp[m - 1][n - 1];
        }

public static int minPathSumOptimized(int[][] grid) {
        int length = grid[0].length;
        int[] dp = new int[length];

        // 初始化
        dp[0] = grid[0][0];
        for (int i = 1; i < dp.length; i++) {
            dp[i] = dp[i-1]+grid[0][i];
        }

        // 关系式
        for (int m = 1; m < grid.length; m++) {
            dp[0] = dp[0] + grid[m][0];
            for (int i = 1; i < length; i++) {
                dp[i] = Math.min(dp[i], dp[i-1])+grid[m][i];
            }
        }

        return dp[length-1];
    }

0 赞同 0 条回复

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

共以下 17 个回答

DP，类比杨辉三角

# 回答此问题取消回复

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

共以下 17 个回答

DP，类比杨辉三角

# 回答此问题 取消回复

# 回答此问题取消回复