原題

給定一個(gè)只含非負(fù)整數(shù)的m*n網(wǎng)格，找到一條從左上角到右下角的可以使數(shù)字和最小的路徑。

你在同一時(shí)間只能向下或者向右移動(dòng)一步

解題思路

• 矩陣型動(dòng)態(tài)規(guī)劃 - Matrix DP
• 與Unique Paths I/II非常類(lèi)似，不同的是每次要找最小value
• cache[i][j]表示從左上角到達(dá)i,j的數(shù)字和最小路徑，它等于cache[i][j - 1]與cache[i - 1][j]的最小值，加上grid[i][j]的值

完整代碼

class Solution(object):
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        if not grid or not grid[0]:
            return 0
        m = len(grid)
        n = len(grid[0])
        cache = [[0 for i in range(n)] for j in range(m)]
        sum1 = sum2 = 0
        for i in range(n):
            sum1 += grid[0][i]
            cache[0][i] = sum1
        for j in range(m):
            sum2 += grid[j][0]
            cache[j][0] = sum2
        for i in range(1, n):
            for j in range(1, m):
                cache[j][i] = min(cache[j - 1][i], cache[j][i - 1]) + grid[j][i]
        return cache[m - 1][n - 1]