#64 Minimum Path Sum——Top 100 Liked Questions

向右看齐 2022-01-29 01:55 126阅读 0赞

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.

> """
> 
> 第一次：动态规划：定义矩阵dp，记录到达当前位置的最短路径之和，分两种情况：1）i=0时，dp\[i\]\[j\]是由grid\[i\]\[j\]与dp\[i\]\[j-1\]的和，只能从左边过来，j=0时，dp\[i\]\[j\]是由grid\[i\]\[j\]与dp\[i-1\]\[j\]的和，只能从上边过来；2）其它情况，可以从左边或者上边过来，取当前位置之前的左边路径或上边路径的最小值，就是到达当前位置的最小值  
> """
> 
>     class Solution(object):
>         def minPathSum(self, grid):
>             """
>             :type grid: List[List[int]]
>             :rtype: int
>             """
>             if not grid:
>                 return 0
>             m = len(grid)
>             n = len(grid[0])
>             if m == 1 and n == 1:
>                 return grid[0][0]
>             dp = [[0 for i in range (n)] for j in range (m)]
>             dp[0][0] = grid[0][0]
>             for i in range(m):
>                 for j in range(n):
>                     if i == 0 and j != 0:
>                         dp[i][j] = dp[i][j - 1] + grid[i][j]
>                         continue
>                     if j == 0 and i != 0:
>                         dp[i][j] = dp[i - 1][j] + grid[i][j]
>                         continue
>                     dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1])
>             return dp[m - 1][n - 1]
> 
> """
> 
> Runtime: 100 ms, faster than 31.97% of Python online submissions for Minimum Path Sum.
> 
> Memory Usage: 13.1 MB, less than 20.83% of Python online submissions for Minimum Path Sum.
> 
> """