64. 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.

Example:

Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

题意

这道题的意思是给你一个二维数组，每个位置的元素代表当前步的距离，求从左上角到右下角的最短距离

是一道动态规划的题目，思路是除了边界上的位置，每一个位置(i,j)的最短距离是上面(i,j-1)和左面(i-1,j)路径之一，由于这里没有限制不能修改原数据，所以可以在原数组grid上做dp

递推公式是：\(dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]\)

时间复杂度O(mn)，空间复杂度O(1)

解法

class Solution:
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        m = len(grid)
        n = len(grid[0])
        
        for row in range(m):
            for col in range(n):
                if row == 0 and col == 0:
                    grid[row][col] = grid[row][col]
                elif row == 0:
                    grid[row][col] += grid[row][col-1]
                elif col == 0:
                    grid[row][col] += grid[row-1][col]
                else:
                    grid[row][col] += min(grid[row][col-1], grid[row-1][col])
        return grid[m-1][n-1]

LeetCode 64. Minimum Path Sum

Dynamic Programming

64. Minimum Path Sum

题意

解法

CATALOG

FEATURED TAGS