120. 三角形最小路径和

题目链接：https://leetcode-cn.com/problems/triangle/
难度：中等

描述：
给定一个三角形 triangle ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

题解

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        n = len(triangle)
        r = [[0] * n for _ in range(n)]
        r[-1] = triangle[-1]
        # 自底向上
        for i in range(n-2, -1, -1):
            for j in range(0, i+1):
                r[i][j] = min(r[i+1][j], r[i+1][j+1]) + triangle[i][j]
        return r[0][0]

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        n = len(triangle)
        r = [0] * (n + 1)
        for i in range(n-1, -1, -1):
            # r[j]保存到triangle[i][j]的最小路径和
            for j in range(0, i+1):
                r[j] = min(r[j], r[j+1]) + triangle[i][j]
        return r[0]