Minimum Path Sum

• tags: [DP_Matrix]

Question

• leetcode64
• lintcode: (110) Minimum Path Sum

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.

题解

1. State: f[x][y] 从坐标(0,0)走到(x,y)的最短路径和
2. Function: f[x][y] = (x, y) + min{f[x-1][y], f[x][y-1]}
3. Initialization: f[0][0] = A[0][0], f[i][0] = sum(0,0 -> i,0), f[0][i] = sum(0,0 -> 0,i)
4. Answer: f[m-1][n-1]

注意最后返回为f[m-1][n-1]而不是f[m][n].

• reference

class Solution:
    # @param grid, a list of lists of integers
    # @return an integer

    def minPathSum(self, grid):
        m = len(grid)
        n = len(grid[0])
        dp = [[0 for i in range(n)] for j in range(m)]
        dp[0][0] = grid[0][0]
        for i in range(1, n):
            dp[0][i] = dp[0][i - 1] + grid[0][i]
        for i in range(1, m):
            dp[i][0] = dp[i - 1][0] + grid[i][0]
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
        return dp[m - 1][n - 1]

sol = Solution()
grid = [[1, 2, 3, 4],
        [4, 5, 6, 7],
        [8, 9, 10, 11]]
sol.minPathSum(grid)

• reference

class Solution(object):
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        m,n = len(grid),len(grid[0])
        ans = [[0 for i in range(n)] for j in range(m)]
        ans[0][0] = grid[0][0]
        for i in range(m):
            for j in range(n):
                if i !=0 and j == 0:
                    ans[i][j] = ans[i-1][j] + grid[i][j]
                elif i == 0 and j != 0:
                    ans[i][j] = ans[i][j - 1] + grid[i][j]
                elif i != 0 and j != 0:
                    ans[i][j] = min(ans[i - 1][j],ans[i][j - 1]) + grid[i][j]
        return ans[m - 1][n - 1]
sol = Solution()
grid = [[1, 2, 3, 4],
        [4, 5, 6, 7],
        [8, 9, 10, 11]]
sol.minPathSum(grid)