华为 OD 训练营 · 题解精讲
LC120. 三角形最小路径和
配套讲解：视频讲解 ↗
LC120. 三角形最小路径和 视频地址：https://uha.xet.tech/s/1jtcg5
题目描述
给定一个三角形 triangle ，找出自顶向下的最小路径和。 每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
题目解析
解题思路
本题要求从三角形顶部到底部的最小路径和，每一步只能移动到下一行的相邻节点（下标相同或下标+1）。参考代码采用自底向上动态规划，核心思想是从最后一行开始，逐层向上计算每个位置的最小路径和。
使用一维数组 dp 进行空间优化，dp[j] 表示到达当前层第 j 个节点的最小路径和。由于每一层的计算只依赖下一层的 dp[j] 和 dp[j+1]，因此可以复用同一个数组，从后向前更新。
关键步骤
1. 初始化：dp 长度为 n+1，初始全为 0。多出的一个位置用于处理边界（最后一行的 j+1 不会越界）。 2. 从最后一行向上遍历：i 从 n-1 到 0，对第 i 行的每个位置 j（0 到 i）：
dp[j] = triangle[i][j] + min(dp[j], dp[j+1])- 其中
dp[j]和dp[j+1]是下一行对应两个相邻节点的最小路径和。
3. 返回结果：dp[0] 即为顶部节点的最小路径和。
示意图（以三角形 [[2],[3,4],[6,5,7]] 为例，自底向上更新过程）：
初始 dp: [0,0,0,0]
第2行(6,5,7): dp = [6,5,7,0] (实际更新为 [6,5,7,0])
第1行(3,4): dp[0]=3+min(6,5)=8, dp[1]=4+min(5,7)=9 → dp=[8,9,7,0]
第0行(2): dp[0]=2+min(8,9)=10 → dp=[10,9,7,0]
返回 dp[0]=10复杂度分析
- 时间复杂度：O(n²)，其中 n 是三角形的行数。需要遍历所有节点，共 n(n+1)/2 个。
- 空间复杂度：O(n)，使用一维数组 dp，长度为 n+1。
参考代码
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
# triangle 是个二维数组
# 先获取 triangle 的层数，即一维数组的个数
n = len(triangle)
# 设置一个一维数组，动态的更新每一层中当前节点对应的最短路径
dp = [ 0 for _ in range( n + 1 )]
# 从最后一层开始计算节点的最短路径，直到顶层 0 层为止
for i in range( n - 1 , -1 , -1) :
# dp 中存储的是前 i 个位置存储的是到达第 i 层各个节点的最小路径和
# 从每一层的第 0 个位置开始
for j in range( 0 , i + 1 ) :
# dp[j] 表示第 i 层中第 j 个节点的最小路径和
dp[j] = triangle[i][j] + min(dp[j],dp[j+1])
# 返回结果
return dp[0]
自顶向下正序遍历写法（许老师）