Minimum Path Sum

Question

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.

Tags

• Array
• Dynamic Programming

Thought

Here we use the dynamic programming to solve the problem:

1. Define a DP table (we use an array to represent the DP table here)
2. Initialize the DP table with the first row in the grid
3. Update the DP table in the loop from the second row to the last row.

recursive equation dp[j] = grid[i][j] + min(dp[j - 1], dp[j])

Code

class Solution(object):
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        if not grid[0]:
            return 0
        height = len(grid)
        width = len(grid[0])
        dp = [0 for _ in xrange(width)]
        # initialization
        dp[0] = grid[0][0]
        for i in xrange(1, width):
            dp[i] = dp[i - 1] + grid[0][i]
        for i in xrange(1, height):
            dp[0] = dp[0] + grid[i][0]
            for j in xrange(1, width):
                dp[j] = grid[i][j] + min(dp[j - 1], dp[j])
        return dp[-1]