120. Triangle

Triangle - LeetCodeLeetCode

核心思路：到达当前点的最小路径由到达上方两个点的最小路径决定，不考虑 edge case 的话，状态转移方程是：

minPath[i][j] = min(minPath[i-1][j], minPath[i-1][j-1]) + triangle[i][j]

到达当前点 (i, j) 的最小路径等于：到达上方两个点 (i-1, j) (i-1, j-1) 的最小路径，加上 (i, j) 的值本身。

每个点的最小路径都存储的话，会要O(n**2/2) 的空间，题目要求 O(n) 的额外空间，可以考虑直接 inplace 操作，我们是按顺序（上->下，左->右）遍历的，直接用 minPath 替换掉原 triangle 的值，这样应该是 O(1).

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        # 从1开始，第0行的最小路径是它值本身，不用更新
        for i in range(1, len(triangle)):
            for j in range(len(triangle[i])):
                # edge case 1
                if j == 0:
                    triangle[i][j] = triangle[i-1][j] + triangle[i][j]
                # edge case 2
                elif j == len(triangle[i])-1:
                    triangle[i][j] = triangle[i-1][j-1] + triangle[i][j]
                else:
                    triangle[i][j] = min(triangle[i-1][j], triangle[i-1][j-1]) + triangle[i][j]
        return min(triangle[len(triangle)-1])

看了下别人的解，直接滚动保存前一行数据，也可以实现 O(n) 复杂度，也避免了 inplace 操作。