京公网安备11010502063487号给定一个三角形数组，求从顶部到底部的最小路径和，每一步只能移动到下一行相邻的两个数字之一。一个很直觉但错误的思路是每一步都贪心地选数值较小的那个，这忽略了"眼前更小"的选择可能会把你带进后面全是大数字的死路。本文构造一个真实反例，其中贪心算出 101、正确答案却只有 2，并用 2 万组随机三角形验证：近三分之一的随机三角形会让贪心策略给出错误答案。再给出正确的自底向上 DP 写法、5 种语言实现，以及逐层取最小子问题的分步演示。
本文只用自己的话概括题意，完整约束以官方页面为准。给定一个三角形数组，求从顶部到底部的最小路径和：每一步只能移动到下一行相邻的两个数字之一（下标 j 或 j+1）。一共 5 组用例，覆盖：官方示例、单行、构造的反例、简单两行三角形、含负数：
[[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]] → 11 [[-10]] → -10 [[0], [1, 2], [100, 100, 0]] → 2 [[1], [2, 3]] → 3 [[1], [-2, -3]] → -2
一个很直觉但错误的思路：既然每一步都要在两个数字之间选一个，那就每步贪心地选数值较小的那个，最后把选过的数字加起来。这个想法忽略了一件事——这道题要的是全局最优的路径和，而"眼前更小"的选择可能会把你带进后面全是大数字的死路，错过后面能连上一串小数字的另一条路。构造一个反例：
triangle = [[0], [1, 2], [100, 100, 0]]\n正确写法（自底向上 DP） → 2\n陷阱写法（每步贪心选较小的） → 101
贪心写法在第二行会选择数值较小的 1（而不是 2），但选了 1 之后，它在第三行能碰到的两个数字都是 100；如果第二行选了看起来更大的 2，第三行却能碰到一个 0，最终路径和反而小得多。这个反例里贪心比最优解差了 99。为了确认这不是个例，做了一次随机测试：
20,000 组随机三角形（深度 2-8，值 0-20）：\n贪心写法与 DP 正确写法结果不同的有 6,323 组，占 31.6%
接近三分之一的随机三角形会让"每步选眼前更小的"这个贪心策略给出错误答案——因为局部最优和全局最优在这类问题里并不等价，只有通过动态规划把"从这一点往下走的最小代价"逐层算清楚，才能保证最终答案是真正的全局最小值。
自底向上：用最后一行直接初始化一个 dp 数组（此时每个位置到底部的最小代价就是它自己），然后从倒数第二行开始往上，每个位置的答案是 自己的值 + min(正下方, 右下方) 这两个已经算好的子问题。滚动更新到 dp[0] 就是从顶部出发的全局最小路径和。时间 O(n²)，空间 O(n)（把 dp 数组原地复用，不需要存整个三角形的副本）。Python、Java、Go、JavaScript、C++ 都是真实编译运行的，用同一组 5 个测试用例。
Python · 解法代码def minimum_total(triangle): n = len(triangle) dp = triangle[-1][:] # 从最后一行开始，自底向上 for i in range(n - 2, -1, -1): for j in range(i + 1): dp[j] = triangle[i][j] + min(dp[j], dp[j + 1]) return dp[0] if dp else 0
$ python3 solution.py [[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]] → 11 [[-10]] → -10 [[0], [1, 2], [100, 100, 0]] → 2 [[1], [2, 3]] → 3 [[1], [-2, -3]] → -2
Java · 解法代码class Solution { public 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] = triangle.get(i).get(j) + Math.min(dp[j], dp[j + 1]); } } return n == 0 ? 0 : dp[0]; } }
$ javac -d build Main.java && java -cp build Main [[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]] → 11 [[-10]] → -10 [[0], [1, 2], [100, 100, 0]] → 2 [[1], [2, 3]] → 3 [[1], [-2, -3]] → -2
Go · 解法代码func minimumTotal(triangle [][]int) int { n := len(triangle) if n == 0 { return 0 } dp := make([]int, n) copy(dp, triangle[n-1]) for i := n - 2; i >= 0; i-- { for j := 0; j <= i; j++ { m := dp[j] if dp[j+1] < m { m = dp[j+1] } dp[j] = triangle[i][j] + m } } return dp[0] }
$ go run solution.go [[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]] → 11 [[-10]] → -10 [[0], [1, 2], [100, 100, 0]] → 2 [[1], [2, 3]] → 3 [[1], [-2, -3]] → -2
JavaScript · 解法代码function minimumTotal(triangle) { const n = triangle.length; if (n === 0) return 0; const dp = [...triangle[n - 1]]; for (let i = n - 2; i >= 0; i--) { for (let j = 0; j <= i; j++) { dp[j] = triangle[i][j] + Math.min(dp[j], dp[j + 1]); } } return dp[0]; }
$ node run.js [[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]] → 11 [[-10]] → -10 [[0], [1, 2], [100, 100, 0]] → 2 [[1], [2, 3]] → 3 [[1], [-2, -3]] → -2
C++ · 解法代码int minimumTotal(vector<vector<int>>& triangle) { int n = triangle.size(); if (n == 0) return 0; vector<int> dp = triangle[n-1]; for (int i = n-2; i >= 0; i--) { for (int j = 0; j <= i; j++) { dp[j] = triangle[i][j] + min(dp[j], dp[j+1]); } } return dp[0]; }
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin [[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]] → 11 [[-10]] → -10 [[0], [1, 2], [100, 100, 0]] → 2 [[1], [2, 3]] → 3 [[1], [-2, -3]] → -2
共 5 组用例（含边界），以 Python 结果为基准逐组比对：\n Python 通过 5/5\n Java 通过 5/5\n Go 通过 5/5\n JavaScript 通过 5/5\n C++ 通过 5/5
Python 版本的自底向上实现另外和一个自顶向下、带记忆化的递归版本做了随机对拍：dfs(i, j) 表示从第 i 行第 j 个位置出发到底部的最小路径和，递归到最后一行直接返回自身的值。
随机对拍 5,000 组（深度 1 到 10 的随机三角形，值取 -20 到 20），自底向上版与自顶向下记忆化版的结果全部一致，0 处不一致。
另外四种语言只在上面 5 组固定用例上验证过，没有做大规模随机对拍。
下面的演示用本文构造的反例 triangle=[[0],[1,2],[100,100,0]]：dp 数组从最后一行开始，每往上一行就用"自己的值 + 下方两个已经算好的最小代价中较小的一个"来更新。蓝色是本轮正在更新的位置，绿色是已经算好、代表"从这里往下走的最优子结构"的位置。每一帧都是把上面的解法在这组输入上真实执行记录下来的——对照本文"陷阱"一节，能清楚看到 DP 在第1行同时算出了 dp[0]=101 和 dp[1]=2 两个选项，而贪心只会盯着眼前的 triangle[1][0]=1 更小就一头扎进去，根本不会去比较"往下走到底"的真实代价。