三角形最小路径和

难度: Medium

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是下标与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

示例 1：

输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
   2
  3 4
 6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

示例 2：

输入：triangle = [[-10]]
输出：-10

提示：

1 <= triangle.length <= 200
triangle[0].length == 1
triangle[i].length == triangle[i - 1].length + 1
-10⁴ <= triangle[i][j] <= 10⁴

进阶：

你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题吗？

注意：本题与主站 120 题相同： https://leetcode-cn.com/problems/triangle/

Submission

运行时间: 24 ms

内存: 17.6 MB

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        n=len(triangle)
        dp=[ [0]*i for i in range(1,n+1) ]
        dp[0][0]=triangle[0][0]
        for i in range(1,n):
            # 边界
            dp[i][0]=dp[i-1][0]+triangle[i][0]
            dp[i][i]=dp[i-1][i-1]+triangle[i][i]
            for j in range(1,i):
                dp[i][j]=min(dp[i-1][j],dp[i-1][j-1])+triangle[i][j]
        return min(dp[n-1])

Explain

此题解使用动态规划来解决三角形最小路径和的问题。我们定义一个二维数组 dp，其中 dp[i][j] 表示从顶部到达第 i 行第 j 列位置的最小路径和。初始化 dp[0][0] 为 triangle[0][0]，即顶点值。对于每一行，处理两个边界情况：dp[i][0] 只能从 dp[i-1][0] 转移而来，dp[i][i] 只能从 dp[i-1][i-1] 转移而来。对于非边界位置 j (1 <= j < i)，dp[i][j] 可以从 dp[i-1][j] 或 dp[i-1][j-1] 转移而来，取二者的最小值再加上当前位置的值 triangle[i][j]。最终，最后一行的最小值即为整个三角形的最小路径和。

时间复杂度: O(n^2)

空间复杂度: O(n^2)

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        n = len(triangle)
        dp = [[0] * i for i in range(1, n + 1)]
        dp[0][0] = triangle[0][0]  # 初始化顶点
        for i in range(1, n):
            dp[i][0] = dp[i - 1][0] + triangle[i][0]  # 处理左边界
            dp[i][i] = dp[i - 1][i - 1] + triangle[i][i]  # 处理右边界
            for j in range(1, i):
                dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i][j]  # 中间位置的状态转移
        return min(dp[n - 1])  # 获取最后一行的最小值

Explore

在动态规划解法中，选择从上到下计算路径和有几个原因。首先，根据题意，路径是从三角形的顶部开始向下延伸，因此从上到下的方法直观且符合问题的自然顺序。其次，这种方式可以在遍历每一行时直接利用上一行的结果，避免了额外的逆向逻辑处理。此外，从上到下的方法允许我们在遍历过程中即时更新状态，而不需要额外的空间来存储从底部开始的中间结果，从而在空间效率上更优。

初始化`dp[0][0]`为`triangle[0][0]`是因为在动态规划中，我们需要一个起始条件来推导后续的状态。在这个问题中，`dp[0][0]`表示从三角形顶点到达顶点自己的最小路径和。因为顶点到顶点的路径只包含顶点本身，所以最小路径和就是顶点的值，即`triangle[0][0]`。这个初始化是整个状态转移的基础，确保了计算的正确开始。

在处理三角形的每一行时，左右边界情况需要特殊处理，因为边界位置只有一种路径选择。对于左边界（即列索引 j=0 的位置），状态转移方程是 `dp[i][0] = dp[i-1][0] + triangle[i][0]`，意味着当前位置的最小路径和只能从上一行同列的位置转移而来，加上当前行的值。对于右边界（即列索引 j=i 的位置，i 表示行索引），状态转移方程是 `dp[i][i] = dp[i-1][i-1] + triangle[i][i]`，意味着当前位置的最小路径和只能从上一行的前一列转移而来，加上当前行的值。这两个方程确保了动态规划在处理边界时的正确性和完整性。