招舟子普通 2023年12月6日下午12:37

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] =grid[i][j]+Math.min(dp[i-1][j],dp[i][j-1]);
}
}
return dp[grid.length-1][grid[0].length-1];
}
}
时间复杂度：O(mn)
空间复杂度：O(mn)

0 赞同 0 条回复

九号球普通 2023年12月2日下午8:47

“`java
class Solution {
public int minPathSum(int[][] grid) {
//dp[i][j]表示从grid[0][0]到grid[i][j]的最小路径，则结果就是dp[m-1][n-1]
//dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
//当i为0时，只有一条路径
int m = grid.length;
int n = grid[0].length;
//优化成一维数组的话，dp[i] = Math.min(dp[i – 1], dp[i]) + grid[i][j];
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++) { for (int j = 0; j < n; j++) { 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]; } }

0 赞同 0 条回复

张开怀普通 2023年7月24日下午12:36

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        if (grid.size() == 0 || grid[0].size() == 0) {
            return 0;
        }
        int rows = grid.size(), columns = grid[0].size();
        auto dp = vector < vector <int> > (rows, vector <int> (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];
    }
};

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

0 赞同 0 条回复

慎言永久会员 2023年7月23日下午5:13

c++实现

class Solution {
public:
int minPathSum(vector<vector>& grid) {
int N=210;
int n=grid[0].size();
int m=grid.size();
if(m<0 || n<0)
return 0;
int dp[N][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]=min(dp[i-1][j],dp[i][j-1])+grid[i][j];
return dp[m-1][n-1];
}
};

0 赞同 0 条回复

Dsjh 普通 2023年7月23日上午12:16

MY

// 参考 62 63
class Solution {
public:
    vector<vector<int>> v;
    int minPathSum(vector<vector<int>>& grid) {
        v = vector<vector<int>>(grid.size(),vector<int>(grid[0].size(),INT_MAX));
        for(int i=0;i<grid.size();i++){
            for(int j=0;j<grid[0].size();j++){
                if(!i && !j){
                    v[i][j] = grid[i][j];
                }
                else{
                    if(i) v[i][j] = min(v[i][j],v[i-1][j]+grid[i][j]);
                    if(j) v[i][j] = min(v[i][j],v[i][j-1]+grid[i][j]);
                }
            }
        }
        return v[grid.size()-1][grid[0].size()-1];
    }
};

0 赞同 0 条回复

BOZ 普通 2023年7月22日上午10:34

【思路】DP思想，dp[i][j]代表从grid[0][0]走到grid[i][j]的最大路径，使用的中间变量可以优化为一维
【复杂度】时间复杂度O(mn)，空间复杂度O(m)/O(n)

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        // dp[i][j] is the min path from grid[0][0] to grid[i][j]
        int m = grid.size(), n = grid[0].size();

        // initialize dp array
        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];

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

        return dp[n - 1];
    }
};

0 赞同 0 条回复

哈哈哈哈开开心心普通 2023年7月22日上午10:22

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:

        m, n = len(grid), len(grid[0])
        dp = [0] * n

        for i in range(m):
            for j in range(n):
                if j == 0:
                    dp[j] = dp[j] + grid[i][j]
                elif i == 0:
                    dp[j] = dp[j - 1] + grid[i][j]
                else:
                    dp[j] = min(dp[j], dp[j - 1]) + grid[i][j]

        return dp[n - 1]

使用滚动数组

0 赞同 0 条回复

花老爷普通 2023年7月21日上午11:42

动态规划
时间：O(mn)
空间：O(1)，题目grid不计入

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        for(int i = 1; i < m; i++) {
            grid[i][0] += grid[i - 1][0];
        }
        for(int i = 1; i < n; i++) {
            grid[0][i] += grid[0][i - 1];
        }
        for (int r = 1; r < m; r++) {
            for (int c = 1; c < n; c++) {
                grid[r][c] += Math.min(grid[r - 1][c], grid[r][c - 1]);
            }
        }
        return grid[m - 1][n - 1];
    }
}

0 赞同 0 条回复

怀瑾永久会员 2023年7月20日上午8:36

“`C++
int minPathSum(std::vector>& grid) {
int m = grid.size();
int n = grid[0].size();

std::vector<std::vector<int>> dp(m, std::vector<int>(n, 0));
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] = std::min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
    }
}

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

}

“`

0 赞同 0 条回复

局外人普通 2023年7月19日下午8:33

思路：动态规划
时间复杂度：O(mn) 空间复杂度：O(mn)

class Solution {
    public int minPathSum(int[][] grid) {
        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 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 条回复

WhyNot 普通 2023年7月19日下午3:41

int minPathSum(int** grid, int gridSize, int* gridColSize) {
    int rows = gridSize, columns = gridColSize[0];
    if (rows == 0 || columns == 0) {
        return 0;
    }
    int dp[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] = fmin(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
        }
    }
    return dp[rows - 1][columns - 1];
}

时间复杂度是O(mn)
空间复杂度是O(mn)

0 赞同 0 条回复

Ming 普通 2023年7月18日下午9:25

public int minPathSum(int[][] grid) {
        // dp[i][j]的意义 从左上角到达当前位置的最小数字总和，所以dp[m-1][n-1]为所求
        // 关系式:dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
        // 初始值：dp[0][j] = dp[0][j-1] + grid[0][j] 一直往右走 dp[0][0] = grid[0][0] 
        //         dp[i][0] = dp[i-1][0] + grid[i][0] 一直往下走
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m+1][n+1];
        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];
    }

二维数组

    public int minPathSum(int[][] grid) {
        // dp[i][j]的意义 从左上角到达当前位置的最小数字总和，所以dp[m-1][n-1]为所求
        // 关系式:dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
        // 初始值：dp[0][j] = dp[0][j-1] + grid[0][j] 一直往右走 dp[0][0] = grid[0][0] 
        //         dp[i][0] = dp[i-1][0] + grid[i][0] 一直往下走
        int m = grid.length;
        int n = grid[0].length;
        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] = grid[i][0] + dp[0];
            for(int j = 1; j < n; j++) {
                dp[j] = Math.min(dp[j], dp[j-1]) + grid[i][j];
            }
        }
        return dp[n-1];
    }

一维数组

0 赞同 0 条回复

小吕普通 2023年7月18日下午8:37

c++实现动态规划
int minPathSum(vector<vector>& grid) {
int line = grid[0].size();
int row = grid.size();
int dp[row][line];
dp[0][0] = grid[0][0];
for(int i = 1;i<row;i++)
{
dp[i][0] = grid[i][0]+dp[i-1][0];
}
for(int i = 1;i<line;i++)
{
dp[0][i] = grid[0][i]+dp[0][i-1];
}
for(int i = 1;i<row;i++)
{
for(int j = 1;j<line;j++)
{
dp[i][j] = min(dp[i-1][j],dp[i][j-1])+grid[i][j];
}
}
return dp[row-1][line-1];
}

0 赞同 0 条回复

Jerry 普通 2023年7月17日下午11:18

// DP + memo
class Solution {

    int[][] memo;

    public int minPathSum(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        memo = new int[rows][cols];

        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
        return dp(grid, rows - 1, cols - 1);
    }

    private int dp(int[][] grid, int row, int col) {
        // base case
        if (row == 0 && col == 0) {
            return grid[0][0];
        }
        if (row < 0 || col < 0) {
            return Integer.MAX_VALUE;
        }

        // memo缓存
        if (memo[row][col] != -1) return memo[row][col];

        memo[row][col] = Math.min(
                dp(grid, row - 1, col),
                dp(grid, row, col - 1)
        ) + grid[row][col]; //dp 方程
        return memo[row][col];
    }

}

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

0 赞同 0 条回复

mpweixin用户永久会员 2023年7月17日下午10:50

class Solution {
//时间O(mn)  空间O(mn)
    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][j - 1] + grid[i][j],dp[i - 1][j] + grid[i][j]);
            }
        }

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

0 赞同 0 条回复

yxy 普通 2023年7月17日下午1:12

时间复杂度O(mn)

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        for(int i=1;i<m;i++)
            grid[i][0]+=grid[i-1][0];
        for(int j=1;j<n;j++)
            grid[0][j]+=grid[0][j-1];
        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 条回复

Yodl. 普通 2023年7月17日上午11:49

//时间复杂度O(mn)  空间复杂度O(mn)
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m=grid.size(),n=grid[0].size();
        int dp[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]=min(dp[i-1][j],dp[i][j-1])+grid[i][j];
                //dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j];
            }
        }
        return dp[m-1][n-1];
    }
};

//时间复杂度O(mn)  空间复杂度O(1)
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m=grid.size(),n=grid[0].size();
        for(int i=1;i<m;i++)
        {
            grid[i][0]=grid[i-1][0]+grid[i][0];
        }
        for(int j=1;j<n;j++)
        {
            grid[0][j]=grid[0][j-1]+grid[0][j];
        }
        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])+grid[i][j];
                //dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j];
            }
        }
        return grid[m-1][n-1];
    }
};

0 赞同 0 条回复

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

共以下 17 个回答

MY

# 回答此问题取消回复

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

共以下 17 个回答

MY

# 回答此问题 取消回复

# 回答此问题取消回复