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
tql