120. 三角形最小路径和（Triangle）
频次 ★★★ · 难度 🟡 · 高频：腾讯/美团
题目
给定一个三角形（数字三角形），从顶部到底部的最小路径和。每次只能移动到下一行中相邻的节点（下标 i 可移动到 i 或 i+1）。
示例：
输入: [
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
输出: 11 （2 + 3 + 5 + 1 = 11）
思路
自底向上 DP：从倒数第二行开始，每个位置的最小路径和等于该位置的值加上下一行相邻两个位置的最小值。原地修改（或一维滚动数组），最终 triangle[0][0] 即为结果。
代码
public int minimumTotal(List<List<Integer>> triangle) {
int n = triangle.size();
// 从倒数第二行往上推
for (int i = n - 2; i >= 0; i--) {
for (int j = 0; j <= i; j++) {
int min = Math.min(triangle.get(i + 1).get(j),
triangle.get(i + 1).get(j + 1));
triangle.get(i).set(j, triangle.get(i).get(j) + min);
}
}
return triangle.get(0).get(0);
}一维 DP（不修改原数据）：
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 dp[0];
}复杂度
- 时间：O(n²) — 遍历所有元素
- 空间：原地修改 O(1)；一维 DP O(n)
边界条件
- 只有一行（
n = 1）：直接返回triangle[0][0]。 - 空三角形：返回 0（或根据题目约束，三角形至少有一行）。
- 负数：路径和可能为负数，不能初始化为 0。
变式
- 自顶向下 DP：从顶部往下推，最后取最后一行的最小值；需要处理边界（每行首尾只有一条路径）。
- 二维网格最小路径和（64. 最小路径和）：矩形网格版，从左上到右下，只能右移或下移。
- 不同路径（62. 不同路径）：求方案数而不是路径和。
易错点
- 原地修改会改变原始三角形数据，面试时应先询问是否允许修改输入。
- 自顶向下时注意首尾只取一个相邻节点（
j = 0时只加dp[j]；j = i时只加dp[j-1]），而自底向上每步都是两个选最小，逻辑统一更不容易出错。 - 一维 DP 中
dp[j]和dp[j + 1]必须从前往后还是从后往前？自底向上时从左到右更新即可，因为dp[j]被覆盖后不影响dp[j+1]的计算（因为dp[j+1]不依赖dp[j]的新值）。
面试追问
- 自顶向下和自底向上哪个更好？ 自底向上不需要处理边界（每行首尾的特殊情况），代码更简洁；自顶向下更符合人类思考方向，但需要额外处理边界。面试中推荐自底向上。
- 空间能优化到 O(1) 吗？ 如果允许修改输入，原地修改就是 O(1)；不允许则至少 O(n)（一维 DP）。
- 如果三角形行数非常大，内存放不下怎么办？ 可以使用外部存储分块读取，但面试中一般不会深究。