• 注册
    • 查看作者
    • LeetCode 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: 7Explanation: Because the path 1→3→1→1→1 minimizes the sum.

      class Solution:
          def minPathSum(self, grid: List[List[int]]) -> int:
              h, w = len(grid), len(grid[0])
              
              result = [[0 for i in range(w)] for j in range(h)]   
              
              result[0][0] = grid[0][0]
              
              for i in range (1,w):
                  result[0][i] = result[0][i-1] + grid[0][i]
              for i in range (1,h):
                  result[i][0] = result[i-1][0] + grid[i][0]
              for i in range (1,h):
                  for j in range(1,w):
                      result[i][j] = min(result[i-1][j],result[i][j-1]) + grid[i][j]
              return result[h-1][w-1]
              print(result)

      [[0,0,0]      [[1,0,0]        [[1,4,5]       [[1,4,5]        [[1,4,5] 

       [0,0,0] →   [0,0,0]  →    [0,0,0]  →  [2,0,0]   →   [2,0,0]             

       [0,0,0]]      [0,0,0]]        [0,0,0]]       [6,0,0]]        [6,0,0]]    

      compare up-left for minimum,

      and add original till the end

      纽约州·法拉盛
    • 0
    • 0
    • 0
    • 334
    • 请登录之后再进行评论

      登录
    • 做任务