64. Minimum Path Sum

# Medium

Is very similar to #62.

1. minPath represents minimum path instead of possible paths.

2. minPath initilizes each edge element: minPath[x][y]=grid[x][y].

Solution:

1. Initilize minPath[0][0] = grid[0][0]

2. Initilize the edge elements of minPath: minPath[x][y] = grid[x][y]+grid[0][0]

3. Initilize other elements of minPath: minPath[x][y] = min(minPath[x-1][y], minPath[x][y-1]) + grid[x][y]

Java(O(mn)

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

Python

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        # initialize minPath
        m = len(grid)
        n = len(grid[m-1])
        minPath = [[-1]*n for i in range(m)]
        minPath[0][0] = grid[0][0]
        
        # initialize fixed part of minPath
        for x in range(1, m):
            minPath[x][0] = grid[x][0] + minPath[x-1][0]
        for y in range(1, n):
            minPath[0][y] = grid[0][y] + minPath[0][y-1]
            
        # compute other element of minPath
        for x in range(1, m):
            for y in range(1, n):
                minPath[x][y] = min(minPath[x-1][y], minPath[x][y-1]) + grid[x][y]
                
        return minPath[m-1][n-1]