首页 > 代码库 > Leetcode 64. Minmum Path Sum
Leetcode 64. Minmum 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.
思路:一个很典型的DP问题。由于只能向下或者右走,所以通过 [i,j] 这个点的最短路径,要么是从[i-1,j]过来,要么从[i,j-1]过来。注意当i=0和j=0时这两个边界特例。
1 class Solution(object): 2 def minPathSum(self, grid): 3 """ 4 :type grid: List[List[int]] 5 :rtype: int 6 """ 7 m = len(grid) 8 n = len(grid[0]) 9 minSum = [[0]*n for x in range(m)] 10 11 for i in range(m): 12 for j in range(n): 13 if i == 0 and j == 0: 14 minSum[0][0] = grid[0][0] 15 elif i == 0: 16 minSum[i][j] = minSum[i][j-1] + grid[i][j] 17 elif j == 0: 18 minSum[i][j] = minSum[i-1][j] + grid[i][j] 19 else: 20 minSum[i][j] = min(minSum[i-1][j], minSum[i][j-1]) + grid[i][j] 21 22 return minSum[-1][-1]
Leetcode 64. Minmum Path Sum
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。