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]
网友评论