064.Minimum Path Sum

Posted on | In

Solution 1: accepted 5ms

DP.
Time: O(n)
Space: O(n) (extra space 0)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public 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] + grid[i][j-1];
                else if (j == 0)
                    grid[i][j] = grid[i][j] + grid[i-1][j];
                else
                    grid[i][j] = grid[i][j] + Math.min(grid[i][j-1], grid[i-1][j]);
            }
        }
        return grid[grid.length-1][grid[0].length-1];
    }
}