三角形最小路径和

题目：

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。

示例：

给定三角形：
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
说明：
如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。

思路：动态规划

因为每一层都依赖上一层的结果，所以只需要一维数组即可，用res[j]表示，每一行路径经过j这个位置的长度。
很容易得到转移方程：i表示层数

res[j] = int(min(triangle[i][j] + res[j-1], triangle[i][j] + res[j]))，if j-1>=0 and j < len(triangle[i-1])

需要注意，由于需要用到上一层的结果，并且把新的结果写入，因此我们从右向左计算res[]。

代码：

class Solution(object):
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        n = len(triangle)

        res = [0] * n
        res[0] = triangle[0][0]

        for i in range(1, n): # 三角形的层数
            for j in range(len(triangle[i])-1, -1, -1): # 反向遍历
                temp1 = float("inf")
                temp2 = float("inf")
                if j - 1 >= 0:
                    temp1 = triangle[i][j] + res[j-1]
                if j < len(triangle[i-1]):
                    temp2 = triangle[i][j] + res[j]
                res[j] = int(min(temp1, temp2))
        
        return min(res)

本文地址：https://blog.csdn.net/zhang_han666/article/details/109647105