数塔问题是动态规划最经典的入门题：从塔顶向下走，每步只能走到下一行的相邻两个位置之一（正下方或右下方），求路径上数字之和的最大值。
什么是”递推”
递推是 DP 的本质 —— 用已经算过的小问题答案，组合出大问题的答案。爬楼梯、斐波那契、数塔，它们的结构都长这样：
| 问题 | 递推关系 |
|---|---|
| 爬楼梯（每次走 1 或 2 阶） | f(n) = f(n-1) + f(n-2) |
| 斐波那契 | F(n) = F(n-1) + F(n-2) |
| 数塔（自底向上） | dp[i][j] = a[i][j] + max(dp[i+1][j], dp[i+1][j+1]) |
共同点：当前状态只看若干个更小（或更靠下/靠后）的状态。把这些”小答案”按顺序算出来存表里，最后查表得到大问题答案 —— 这就是 DP 的起手式。
数塔自底向上
定义 dp[i][j] = 从 (i, j) 出发到塔底的最大路径和。
边界：最底层 dp[n-1][j] = a[n-1][j]（已经在塔底，再不能走）
递推：dp[i][j] = a[i][j] + max(dp[i+1][j], dp[i+1][j+1])
从倒数第二行开始自底向上填表，最后 dp[0][0] 就是答案。
为什么自底向上更自然
也可以自顶向下定义 dp[i][j] = 从塔顶到 (i, j) 的最大路径和，最后取最后一行的最大值。两种方向都对，但自底向上的好处是答案直接落在 dp[0][0]，不需要再扫一遍最后一行取 max。
复杂度
- 时间：O(n²) — 三角形一共 n(n+1)/2 个格子，每个 O(1)
- 空间：O(n²) 二维 / O(n) 一维滚动（每行只依赖下一行）
在动画里看什么
- 每个格子里上方小字是原值
a[i][j]，下方大字是dp[i][j]（”·” 表示还没算） - 先填充最底层（绿色背景）
- 然后自底向上一行一行算，深蓝是正在计算的格子
- 算完后，从塔顶开始按”邻居谁大就走谁”画出暖红色路径