LC 64 Minimum Path Sum(M)

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

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

public int minPathSum(int[][] grid)

边界条件 保证数组有行列

解题思路 DP

因为不能左或上， 所以 grid[r][c] = min(grid[r-1][c], grip[r][c-1]) + grid[r][c]

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