Leetcode: Minimum Path Sum

Minimum Path Sum | LeetCode OJ

This one can be easily visualized as a dynamic programming problem as the path ending at grid point can either come from the point above it or the point to the left of it. All we need to do is pick the path that gives us minimum sum. The algorithm is

1. Start traversing the matrix from the top left and store sum of values along the path
2. Points on the first row and first column have only one path option so handle them separately
3. All other points have 2 choices, take the path with minimum sum
4. Store all the sums in a dictionary to avoid re computation

Remarks:

1. O(m*n) time complexity
2. O(m*n) space complexity
3. O(1) space complexity can be achieved by storing the path sum in the input grid itself but it is preferable not to modify the input
4. All dynamic programming problems involving a grid can be solved by similar approach. For eg, maximum size sub matrix with all 1's.

class Solution(object):
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        m = len(grid)
        n = len(grid[0])
        dp = [[0] * n] * m
        dp[0][0] = grid[0][0]
        for i in range(m):
            if i > 0:
                dp[i][0] = dp[i - 1][0] + grid[i][0]
            for j in range(1, n):
                if i == 0 and j > 0:
                    dp[i][j] = dp[i][j - 1] + grid[i][j]
                else:
                    dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j]
        return dp[m - 1][n - 1]