【Check 80】2024-05-22 - 64. 最小路径和

[larscheng]

64. 最小路径和

[larscheng]

思路

• dp[i][j]表示到达(i,j)的最小路径和
• dp[i][j] = Min(dp[i][j-1],dp[i-1][j])+grid[i][j]
• 起点的最小路径和为grid[0][0]，dp[0][0] = grid[0][0]
• dp[0][1] = dp[0][0]+grid[0][1]
• i=0时，dp[0][j] = dp[0][j-1]+grid[0][j]
• j=0时，dp[i][0] = dp[i-1][0]+grid[i][0]

  代码

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 j = 1; j < grid[0].length; j++) {
        dp[0][j] = dp[0][j - 1] + grid[0][j];
    }
    for (int i = 1; i < grid.length; i++) {
        for (int j = 1; j < grid[0].length; j++) {
            dp[i][j] = Math.min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j];
        }
    }
    return dp[grid.length - 1][grid[0].length - 1];
}

}

### 复杂度
- 时间复杂度：O(m*n)
- 空间复杂度：O(m*n)

[larscheng]

思路

2维dp数组需要使用额外空间 可以直接在原二维数组上直接操作，记录每个位置的最小路径和 O(m*n)/O(1)

代码

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