三角形最小路径和如何用动态规划求解？为什么从底向上更省边界判断？

简化版

三角形最小路径和可以从底向上做 DP。令 dp[j] 表示从当前层位置 j 走到底部的最小路径和，转移为 dp[j] = min(dp[j], dp[j+1]) + triangle[i][j]，最后 dp[0] 就是答案。

详细版

从顶向下做也可以，但每个位置的父节点数量不同，左右边界要特殊处理。从底向上更自然：每个位置只能走到下一层的 j 或 j+1，因此直接取两个子问题的较小值再加当前值。

可以先把最后一层复制到 dp 数组，然后从倒数第二层往上更新。时间复杂度 O(n²)，其中 n 是层数；空间复杂度 O(n)。如果允许修改原数组，也可以原地更新三角形。

完整版教学

一、三角形 DP 和普通矩阵路径的区别

三角形路径的每一层长度不同，第 i 层有 i+1 个数。位置 (i,j) 的下一步只能走到 (i+1,j) 或 (i+1,j+1)。这和矩阵“右、下”很像，但边界形状不是矩形。

      2
    3   4
  6   5   7
4   1   8   3

如果从顶向下走，左边缘和右边缘只有一个父节点，中间才有两个父节点。边界能处理，但代码容易多写分支。

二、为什么从底向上更顺手

从底向上看，每个格子的选择都很统一：它只需要问下一层的两个孩子哪个更小。无论这个格子是不是边界，都存在 j 和 j+1 两个孩子。

方向	状态含义	边界复杂度
自顶向下	到达当前点的最小和	左右边缘要特殊处理
自底向上	从当前点到底部的最小和	转移统一

易错点：三角形题别急着按矩阵模板写，先看从哪个方向转移边界最少。

自底向上的本质是先知道“下面怎么走最便宜”，再把当前值接上去。

三、状态定义和转移公式

定义一维 dp[j]：

处理到第 i 层时，dp[j] 表示从 triangle[i][j] 走到底部的最小路径和

初始时，dp 就是最后一层：

dp = [4, 1, 8, 3]

往上一层更新：

dp[j] = min(dp[j], dp[j + 1]) + triangle[i][j]

更新后，dp[j] 变成当前层位置 j 的最优答案。因为第 i 层只依赖第 i+1 层，所以可以覆盖。

四、用数字例子完整推演

仍然看这个三角形：

      2
    3   4
  6   5   7
4   1   8   3

最后一层初始化为：

[4, 1, 8, 3]

处理 [6,5,7]：

6 + min(4,1) = 7
5 + min(1,8) = 6
7 + min(8,3) = 10
dp = [7, 6, 10, 3]

再处理 [3,4] 得到 [9,10,...]，最后处理 [2] 得到 11，路径是 2 -> 3 -> 5 -> 1。

五、代码模板

int minimumTotal(List<List<Integer>> triangle) {
    int n = triangle.size();
    int[] dp = new int[n];
    for (int j = 0; j < n; j++) {
        dp[j] = triangle.get(n - 1).get(j);
    }
    for (int i = n - 2; i >= 0; i--) {
        for (int j = 0; j <= i; j++) {
            dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j);
        }
    }
    return dp[0];
}

循环顺序非常重要。外层从下往上，内层从左往右即可，因为 dp[j] 和 dp[j+1] 在本轮更新前都还是下一层的数据。

六、为什么不能简单选较小的孩子

看局部，2 的下一层可以选 3 或 4，选 3 看起来更小。但这只是当前一步小，不代表后面路径总和最小。DP 取的是“孩子节点到底部的最小总成本”，不是孩子节点本身的数值。

错误贪心：当前值 + min(下一层数值)
正确 DP：当前值 + min(下一层完整最优路径)

这也是动态规划和贪心的典型区别：贪心只看眼前选择，DP 把后续代价压缩进子问题答案里。

七、常见误区与追问

误区：把 dp[j+1] 提前覆盖掉。 自底向上一维写法从左到右更新是安全的，因为依赖的是下一层的 dp[j] 和 dp[j+1]。
误区：把路径值和路径下标混在一起。 dp 只保存最小和，如果要输出路径要额外记录选择。
误区：用贪心选下一层较小数字。 较小数字后面可能连接更大代价，不能只看一步。
追问：能不能从顶向下做？ 可以，但要处理左边缘、右边缘和中间位置的不同父节点。
追问：空间为什么是 O(n)？ 每层只依赖下一层，最大层宽是 n。
追问：如果数字有负数还能做吗？ 可以，图仍然是无环层级结构，DP 不受负数影响。

八、加强记忆

三角形最小路径和要记住“站在当前点，看下面两个完整子路径”。从底向上写，边界最干净；dp[j] 和 dp[j+1] 是两个孩子到底部的答案，不是两个孩子的裸数值。这个题考的不是公式复杂，而是你能不能选对转移方向，让代码自然地避开边界坑。

简化版

详细版