【LeetCode】0064 最小路径和

https://leetcode-cn.com/problems/minimum-path-sum/

# -*- coding:utf-8 -*-

class Solution(object):
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        dp = [0] * (len(grid[0]) + 1)
        for i in range(len(grid[0])):
            dp[i] = grid[0][i] + dp[i - 1]
        dp[-1] = float('inf')
        for i in range(1, len(grid)):
            for j in range(len(grid[0])):
                dp[j] = min(dp[j - 1] + grid[i][j], dp[j] + grid[i][j])
        return dp[-2]
if __name__ == '__main__':
    grid = [
        [1, 3, 1],
        [1, 5, 1],
        [4, 2, 1]
    ]
    grid = [[1, 2, 5], [3, 2, 1]]
    print(Solution().minPathSum(grid))

思路：我之前做过时空复杂度都是90多的，但是这道题时空复杂度都接近100，太开心了。

简单说这道题依然是内存优化后的动态规划，因为这次取最小，所以我们将最后一位置为最大。同样，因为当前层是对上一层进行的操作，因此可以将二维dp数组降为一维，使用dp[j] = min(dp[j - 1] + grid[i][j], dp[j] + grid[i][j])来计算i j位置的dp结果。