64. Minimum Path Sum

最后更新

二刷？

和小机器人走路径差不多= =
这个可以在原有的盘子上更新= = 如果不是只读。

Time : O(N) + O(M) + O(M * N)
Space: in-place

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

如果是in-place，依然是一维数组。

2D board使用一维数组要确定2个东西，一个是每一行的初始状态，小机器人里初始状态是0，来自左边是不可能的，只有来自上面一种可能，所以是1.

这里初始无限大。。表示只能选来自上面方向。
第一行的第一个初始状态得是0+格子里的数，后面每行初始设置为无限大就行。

public class Solution {
    public int minPathSum(int[][] grid) {
        if (grid.length == 0) return 0;
        
        int row = grid.length;
        int col = grid[0].length;
        
        int[] dp = new int[col+1];
    
        Arrays.fill(dp, Integer.MAX_VALUE);
        
        dp[0] = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                dp[j+1] = Math.min(dp[j+1], dp[j]) + grid[i][j];
            }
            dp[0] = Integer.MAX_VALUE;
        }
        
        
        return dp[col];
    }
}

这种题的最后挑战就是滚动数组。。

---

一刷。

动态规划，和那个机器人走路的差不多，只不过这次是每个格子有2种可能，左边或者上边，选较小的那个。

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

感觉上是可以不用M*N的extra space。
直接更新在原来的grid上也不是不可以。。