leetcode 64 最小路径和

动态规划的想法，dp数组中存储的位置代表每一条路径到达当前位置的最小路径和，每一个状态进行转移的时候只和左面和上面的位置有关。

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        dp=[[0 for _ in range(len(grid[0]))]for _ in range(3)]
        dp[0][0]=grid[0][0]
        for i in range(1,3):
            dp[i][0]=dp[i-1][0]+grid[i][0]
        for j in range(1,len(grid[0])):

            dp[0][j]=dp[0][j-1]+grid[0][j]



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


        return dp[len(grid)-1][len(grid[0])-1]

空间优化，因为只用到前两行的内容，所以可以进行空间优化，再仔细思考，其实只用到一行，因为左上角的元素已经用不到，可以存储左面的元素。

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        dp=[float('inf') for _ in range(len(grid[0]))]

        #dp[0]=grid[0][0]
        dp[0]=0
        for i in range(len(grid)):
            dp[0]=dp[0]+grid[i][0]
            for j in range(1,len(grid[0])):
                dp[j]=min(dp[j-1]+grid[i][j],dp[j]+grid[i][j])


        return dp[len(grid[0])-1]