LeetCode 120. 三角形最小路径和

字数 2257 2025-12-14 14:01:46

LeetCode 120. 三角形最小路径和

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

示例：
输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：自顶向下的最小路径和为 2 + 3 + 5 + 1 = 11。

解题过程循序渐进讲解

理解问题结构
三角形是一个二维结构，但每一行的长度不同。第 i 行（从0开始）有 i+1 个元素。
从顶部到底部的路径必须满足“相邻”移动规则。目标是找到所有可能路径中，路径上数字总和最小的那个。
初步思考 – 暴力搜索
可以尝试枚举所有路径。从顶部开始，每一步有两个选择（左下或右下），到达底部时，路径数量是指数级的（约 2^(n-1) 条路径，n 为行数）。这在大三角形上会超时，需要优化。
动态规划思路的引入
观察到：到达某个位置 (i, j) 的最小路径和，可以由其上方两个可能来源决定：
- 从左上角 (i-1, j-1) 过来
- 从正上方 (i-1, j) 过来（当 j < i 时存在）
  因此，可以定义 dp[i][j] 表示从三角形顶部走到位置 (i, j) 的最小路径和。
  状态转移方程：
  dp[i][j] = triangle[i][j] + min(dp[i-1][j-1], dp[i-1][j])
  注意边界情况：
  - 当 j == 0 时，只能从正上方来，即 dp[i-1][j]
  - 当 j == i 时，只能从左上角来，即 dp[i-1][j-1]
    最终结果 = min(dp[n-1][j])，对最后一行所有 j 取最小值。
具体计算步骤
以示例 triangle = [[2],[3,4],[6,5,7],[4,1,8,3]] 为例：
初始化 dp[0][0] = 2。
第1行：
dp[1][0] = 3 + dp[0][0] = 5
dp[1][1] = 4 + dp[0][0] = 6
第2行：
dp[2][0] = 6 + dp[1][0] = 11
dp[2][1] = 5 + min(dp[1][0], dp[1][1]) = 5 + 5 = 10
dp[2][2] = 7 + dp[1][1] = 13
第3行：
dp[3][0] = 4 + dp[2][0] = 15
dp[3][1] = 1 + min(dp[2][0], dp[2][1]) = 1 + 10 = 11
dp[3][2] = 8 + min(dp[2][1], dp[2][2]) = 8 + 10 = 18
dp[3][3] = 3 + dp[2][2] = 16
最后一行最小值是 11，即结果。
空间优化
注意到 dp[i] 只与 dp[i-1] 有关，可以用一维数组滚动更新。
从下往上更新（或者从上往下但注意更新顺序），避免覆盖。这里常用从上往下更新，但需要小心：
如果从左到右更新，会覆盖左上角的值，所以可以从右到左更新每一行。
更简单的方法是只用一行 dp，长度等于三角形行数，初始化 dp[0]=triangle[0][0]。
从第1行开始，对每一行从右到左更新：
dp[j] = triangle[i][j] + min(dp[j-1], dp[j])，其中 1 ≤ j ≤ i-1
两端的 dp[0] 和 dp[i] 单独处理（只能从一个来源来）。
这样空间复杂度从 O(n^2) 降到 O(n)。
另一种直观方法：自底向上更新
从倒数第二行开始，向上逐行更新每个位置的最小路径和：
triangle[i][j] += min(triangle[i+1][j], triangle[i+1][j+1])
更新到顶部时，triangle[0][0] 就是最小路径和。
这样做不需要额外空间（直接修改原数组），且逻辑更简洁。
示例自底向上：
第3行不变 [4,1,8,3]
第2行：6+min(4,1)=7, 5+min(1,8)=6, 7+min(8,3)=10 → [7,6,10]
第1行：3+min(7,6)=9, 4+min(6,10)=10 → [9,10]
第0行：2+min(9,10)=11 → 结果 11。
最终算法步骤（自底向上）
a. 从倒数第二行（i = n-2）开始，向上遍历每一行。
b. 对当前行的每个位置 j（0 ≤ j ≤ i），执行：
triangle[i][j] += min(triangle[i+1][j], triangle[i+1][j+1])
c. 遍历结束后，triangle[0][0] 即为最小路径和。
时间复杂度 O(n^2)，空间复杂度 O(1)（不考虑输入存储则 O(1)）。
边界情况
如果三角形只有一行，直接返回该行的唯一值。
如果三角形为空，返回 0（但题目保证至少有一行）。

LeetCode 120. 三角形最小路径和题目描述给定一个三角形 triangle ，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的节点上。相邻的节点在这里指的是下标与上一层节点下标相同，或者等于上一层节点下标 + 1 的两个节点。也就是说，如果当前位于第 i 行的下标 j ，那么下一步可以移动到第 i+1 行的下标 j 或下标 j+1 。示例：输入：triangle = [ [ 2],[ 3,4],[ 6,5,7],[ 4,1,8,3] ] 输出：11 解释：自顶向下的最小路径和为 2 + 3 + 5 + 1 = 11。解题过程循序渐进讲解理解问题结构三角形是一个二维结构，但每一行的长度不同。第 i 行（从0开始）有 i+1 个元素。从顶部到底部的路径必须满足“相邻”移动规则。目标是找到所有可能路径中，路径上数字总和最小的那个。初步思考 – 暴力搜索可以尝试枚举所有路径。从顶部开始，每一步有两个选择（左下或右下），到达底部时，路径数量是指数级的（约 2^(n-1) 条路径，n 为行数）。这在大三角形上会超时，需要优化。动态规划思路的引入观察到：到达某个位置 (i, j) 的最小路径和，可以由其上方两个可能来源决定：从左上角 (i-1, j-1) 过来从正上方 (i-1, j) 过来（当 j < i 时存在）因此，可以定义 dp[ i][ j ] 表示从三角形顶部走到位置 (i, j) 的最小路径和。状态转移方程： dp[ i][ j] = triangle[ i][ j] + min(dp[ i-1][ j-1], dp[ i-1][ j ]) 注意边界情况：当 j == 0 时，只能从正上方来，即 dp[ i-1][ j ] 当 j == i 时，只能从左上角来，即 dp[ i-1][ j-1 ] 最终结果 = min(dp[ n-1][ j ])，对最后一行所有 j 取最小值。具体计算步骤以示例 triangle = [ [ 2],[ 3,4],[ 6,5,7],[ 4,1,8,3] ] 为例：初始化 dp[ 0][ 0 ] = 2。第1行： dp[ 1][ 0] = 3 + dp[ 0][ 0 ] = 5 dp[ 1][ 1] = 4 + dp[ 0][ 0 ] = 6 第2行： dp[ 2][ 0] = 6 + dp[ 1][ 0 ] = 11 dp[ 2][ 1] = 5 + min(dp[ 1][ 0], dp[ 1][ 1 ]) = 5 + 5 = 10 dp[ 2][ 2] = 7 + dp[ 1][ 1 ] = 13 第3行： dp[ 3][ 0] = 4 + dp[ 2][ 0 ] = 15 dp[ 3][ 1] = 1 + min(dp[ 2][ 0], dp[ 2][ 1 ]) = 1 + 10 = 11 dp[ 3][ 2] = 8 + min(dp[ 2][ 1], dp[ 2][ 2 ]) = 8 + 10 = 18 dp[ 3][ 3] = 3 + dp[ 2][ 2 ] = 16 最后一行最小值是 11，即结果。空间优化注意到 dp[ i] 只与 dp[ i-1 ] 有关，可以用一维数组滚动更新。从下往上更新（或者从上往下但注意更新顺序），避免覆盖。这里常用从上往下更新，但需要小心：如果从左到右更新，会覆盖左上角的值，所以可以从右到左更新每一行。更简单的方法是只用一行 dp，长度等于三角形行数，初始化 dp[ 0]=triangle[ 0][ 0 ]。从第1行开始，对每一行从右到左更新： dp[ j] = triangle[ i][ j] + min(dp[ j-1], dp[ j ])，其中 1 ≤ j ≤ i-1 两端的 dp[ 0] 和 dp[ i ] 单独处理（只能从一个来源来）。这样空间复杂度从 O(n^2) 降到 O(n)。另一种直观方法：自底向上更新从倒数第二行开始，向上逐行更新每个位置的最小路径和： triangle[ i][ j] += min(triangle[ i+1][ j], triangle[ i+1][ j+1 ]) 更新到顶部时，triangle[ 0][ 0 ] 就是最小路径和。这样做不需要额外空间（直接修改原数组），且逻辑更简洁。示例自底向上：第3行不变 [ 4,1,8,3 ] 第2行：6+min(4,1)=7, 5+min(1,8)=6, 7+min(8,3)=10 → [ 7,6,10 ] 第1行：3+min(7,6)=9, 4+min(6,10)=10 → [ 9,10 ] 第0行：2+min(9,10)=11 → 结果 11。最终算法步骤（自底向上） a. 从倒数第二行（i = n-2）开始，向上遍历每一行。 b. 对当前行的每个位置 j（0 ≤ j ≤ i），执行： triangle[ i][ j] += min(triangle[ i+1][ j], triangle[ i+1][ j+1 ]) c. 遍历结束后，triangle[ 0][ 0 ] 即为最小路径和。时间复杂度 O(n^2)，空间复杂度 O(1)（不考虑输入存储则 O(1)）。边界情况如果三角形只有一行，直接返回该行的唯一值。如果三角形为空，返回 0（但题目保证至少有一行）。