力扣-64.最小路径和

dp函数 超时

class Solution(object):

    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        m = len(grid)
        n = len(grid[0])
        return self.dp(grid, m - 1, n - 1)

    def dp(self, grid, i, j):
        if i == 0 and j == 0:
            return grid[0][0]
        if i < 0 or j < 0:
            return 99999
        res = min(self.dp(grid, i - 1, j), self.dp(grid, i, j - 1)) + grid[i][j]
        return res

dp函数剪枝 超时

class Solution(object):
    import sys
    sys.setrecursionlimit(1000000)
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        m = len(grid)
        n = len(grid[0])

        return self.dp(grid, m - 1, n - 1)

    def dp(self, grid, i, j):
        m = len(grid)
        n = len(grid[0])
        res = 999999
        memo = [[-1 for i in range(m)] for j in range(n)]
        if i == 0 and j == 0:
            return grid[0][0]
        if i < 0 or j < 0:
            return res
        if memo[i][j] != -1:
            return memo[i][j]
        memo[i][j] = min(self.dp(grid, i - 1, j), self.dp(grid, i, j - 1)) + grid[i][j]
        
        return memo[i][j]

dp数组，表示为从[0,0]走到[i,j]的路径和

class Solution(object):

    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        m = len(grid)
        n = len(grid[0])
        dp = [[0 for i in range(n)] for j in range(m)]

        dp[0][0] = grid[0][0]
        for i in range(1, m):
            dp[i][0] = dp[i - 1][0] + grid[i][0]
        for j in range(1, n):
            dp[0][j] = dp[0][j - 1] + grid[0][j]

        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]

        return dp[m - 1][n - 1]


if __name__ == '__main__':
    grid = [[1, 2, 3], [4, 5, 6]]
    Sol = Solution()
    res = Solution.minPathSum(Sol, grid)
    print(res)