题目描述
三角形数组，每格只能走到下一行相邻两格，求顶到底的最小路径和。
思路解析
最直接的想法：从顶 2 出发，每格分叉走左/右，把所有路径都试一遍取最小。但路径条数随层数翻倍（n 层约 2ⁿ 条）。而且像中间那格 5，会被很多条不同路径反复经过、反复重算它「往下走到底的最小代价」——典型重叠子问题。
换个状态定义：dp[j] = 站在某格、一路走到底的最小路径和。最底层每格走到底就是它自己。往上每格 = 自己 + min(正下方, 右下方)，即 tri[i][j] + min(dp[j], dp[j+1])。为什么能记表？因为每格的答案只依赖下一行那两格，算好就存进 dp，上层直接查、不重算。自底向上还省去了对两条斜边的边界特判。
dp = 最后一行：先把 dp 初始化成三角形最后一行 [4, 1, 8, 3]：站在底层任一格，已经到底了，走到底的代价就是它自己。这一行 4 个值是后面所有计算的依赖来源，整张表固定 1 行 4 列、只覆盖数值不增删。
折叠行 [6,5,7] · 算 dp[0]：开始折入倒数第二行 [6,5,7]。第一格是 6：它正下方是 4、右下方是 1（蓝色两个依赖格），取较小的 1，dp[0] = 6+1 = 7。注意 4 没被选中——这就是"取 min"在做的事。
折叠行 [6,5,7] · 算 dp[1]：第二格是 5：正下方 1、右下方 8，8 这条更大的路被丢弃，取 1，dp[1] = 5+1 = 6。每格都只保留通往底部更便宜的那一支。
折叠行 [6,5,7] · 算 dp[2]：第三格是 7：正下方 8、右下方 3，取 3，dp[2] = 7+3 = 10。这一行折完，dp 前三位变成 [7, 6, 10]（最后一位 3 已用过、作废）。
折叠行 [3,4] · 算 dp[0]：折入第二行 [3,4]。第一格 3：正下方 7、右下方 6，取 6，dp[0] = 3+6 = 9。7 没被选——往左下走更贵。
折叠行 [3,4] · 算 dp[1]：第二格 4：正下方 6、右下方 10，取 6，dp[1] = 4+6 = 10。这一行折完，dp 前两位 = [9, 10]。
折叠顶 [2] · 算 dp[0]：最后折入顶点 2：正下方 9、右下方 10，10 那条更贵被舍弃，取 9，dp[0] = 2+9 = 11。
答案：dp[0] = 11 就是最小路径和。整条最优路径 2→3→5→1，正好对应每一步选中的那个较小依赖格。
当「某格依赖下一行相邻几格」时，自底向上比自顶向下更顺：不用特判第一/最后一列，dp 还能一维原地滚动。下降路径最小和、堆叠 DP 都是这个套路。
参考代码（Python）
1def minimumTotal(self, triangle):
2 dp = triangle[-1][:] # 复制最后一行做底层
3 for i in range(len(triangle) - 2, -1, -1): # 倒数第二行往上
4 for j in range(len(triangle[i])):
5 dp[j] = triangle[i][j] + min(dp[j], dp[j+1]) # 自己+下方较小
6 return dp[0]复杂度分析
- 时间复杂度：O(n²) —— 三角形共约 n²/2 个格子，每格做一次 min 与相加
- 空间复杂度：O(n) —— 只用一维 dp，长度等于底边 n
套路模板
记住骨架：dp 从最底层开始、逐层往上用相邻项聚合折叠。求最小用 min、求最大用 max，结构都一样。
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]（直接引用最后一行） → 正确写法：dp = triangle[-1][:]（复制一份）（不加 [:] 是同一个列表，原地折叠会改写、破坏原三角形数据）
- 错误写法：自顶向下时忘了特判两条斜边 → 正确写法：改用自底向上，每格恒有两个下方来源（顶向下时每行首尾格只有一个上方来源，少特判就会越界或漏路径）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。