三角形最小路径和

https://leetcode-cn.com/explore/interview/card/bytedance/246/dynamic-programming-or-greedy/1030/

image.png

动态规划，找规律吧少年。
其实规律也很好发现，从最后一层往上找，上一层的最小路径，是下一层左右两个节点的最小值加上当前节点的值，这样遍历到第一个节点就好了。
题目要用O(n)空间复杂度，n为三角形高度。其实额外的空间最大的就是最后一层数组的长度，恰好也等于三角形高度，满足需求

class Solution(object):
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        if not triangle:
            return 0
        pos = triangle[-1]
        for i in range(len(triangle)-2,-1,-1):
            for j in range(0,len(triangle[i])):
                pos[j] = min(pos[j],pos[j+1])+triangle[i][j]
        return pos[0]