64 Minimum Path Sum

https://leetcode.com/problems/minimum-path-sum/#/description

Given amxngrid filled with non-negative numbers, find a path from top left to bottom right whichminimizesthe sum of all numbers along its path.

Note:You can only move either down or right at any point in time.

分析及代码

额比预计的简单，只是最最基础的动规。

path[i][j] = Math.min(path[i - 1][j], path[i][j - 1]) + path[i][j];

可以在原板子上操作，初始化就是把第一行/第一列加起来

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

O(mn)