120. 三角形最小路径和

题目描述

三角形数组，每格只能走到下一行相邻两格，求顶到底的最小路径和。

思路解析

自底向上：dp 初始化为最后一行。往上每一行，每格 = 自己 + min(正下方, 右下方) = tri[i][j] + min(dp[j], dp[j+1])。一直折叠到顶，dp[0] 就是答案。这样不用处理边界。

dp = 最后一行：把 dp 初始化成三角形最后一行 [4, 1, 8, 3]——到达底层各格的代价就是它自己。

折叠行 [6,5,7]：折入倒数第二行：每格加下方相邻两个的较小值。dp 变成 [7, 6, 10]（最后一位作废）。

折叠行 [3,4]：再折入 [3,4]：3+min(7,6)=9、4+min(6,10)=10。dp = [9, 10]。

折叠顶 [2]：最后折入顶点 2：2 + min(9, 10) = 11。dp[0] 就是最小路径和。

当「某格依赖下一行相邻几格」时，自底向上比自顶向下更顺：不用特判第一/最后一列，dp 还能一维滚动。

参考代码（Python）

1dp = triangle[-1][:]                  # 复制最后一行
2for i in range(len(triangle) - 2, -1, -1):  # 倒数第二行往上
3    for j in range(len(triangle[i])):
4        dp[j] = triangle[i][j] + min(dp[j], dp[j+1])
5return dp[0]

复杂度分析

• 时间复杂度：O(n²) —— 三角形格子总数
• 空间复杂度：O(n) —— 一维 dp(底边长度)

套路模板

记住骨架：dp 从最底层开始、逐层往上用相邻项聚合折叠。下降路径最小和、堆叠类 DP 都能这么折。

1dp = 最后一层[:]                      # 从底层初始化
2for i in range(倒数第二层, -1, -1):
3    for j in range(本层宽度):
4        dp[j] = a[i][j] + 聚合(dp[j], dp[j+1])  # min/max/加
5return dp[0]

易错点

• ❌ 自顶向下还要特判两条斜边 → ✅ 自底向上无边界更省心（顶向下时每行首尾格只有一个上方来源）
• ❌ dp 直接引用最后一行 → ✅ 复制一份 triangle[-1][:]（原地改会破坏原三角形）

以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。