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结果。

分类: 算法

1 条评论

NPHard · 2020-02-28 00:30

Unknown Unknown Unknown Unknown

tql

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注