[Backtracking/DP]64. Minimum Pat

• 分类：Backtracking/DP
• 时间复杂度: O(n*m)

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.

代码：

记忆化递归方法:

class Solution:
    def minPathSum(self, grid: 'List[List[int]]') -> 'int':
        
        res=0
        if grid==None or len(grid)==0 or len(grid[0])==0:
            return res
        
        m=len(grid)
        n=len(grid[0])
        res=self.paths(m,n,grid,{})
        
        return res
    
    def paths(self,m,n,grid,memo):
        
        if (m,n) in memo:
            return memo[(m,n)]
        
        else:
            
            if m<=0 or n<=0:
                memo[(m,n)]=0
                return memo[(m,n)]
            if m==1 and n==1:
                memo[(m,n)]=grid[m-1][n-1]
                return memo[(m,n)]
            
            if m==1:
                memo[(m,n)]=grid[m-1][n-1]+self.paths(m,n-1,grid,memo)
            elif n==1:
                memo[(m,n)]=grid[m-1][n-1]+self.paths(m-1,n,grid,memo)
            else:
                memo[(m,n)]=grid[m-1][n-1]+min(self.paths(m-1,n,grid,memo),self.paths(m,n-1,grid,memo))
                
            return memo[(m,n)]

DP方法:

import sys
class Solution:
    def minPathSum(self, grid: 'List[List[int]]') -> 'int':
        
        res=0
        if grid==None or len(grid)==0 or len(grid[0])==0:
            return res
        
        m=len(grid)
        n=len(grid[0])
        
        res_matrix=[[sys.maxsize for i in range(n)] for i in range(m)]
        res_matrix[0][0]=grid[0][0]
        for i in range(1,m):
            res_matrix[i][0]=grid[i][0]+res_matrix[i-1][0]
        for j in range(1,n):
            res_matrix[0][j]=grid[0][j]+res_matrix[0][j-1]
        
        for i in range(m):
            for j in range(n):
                if i>0 and j>0:
                    res_matrix[i][j]=grid[i][j]+min(res_matrix[i-1][j],res_matrix[i][j-1])
        
        return res_matrix[-1][-1]

讨论：

1.最后这个DP还是捋了好几遍，如果实在脑子里混乱的话还是先把两边能搞清楚的先搞清楚，然后一步一步的