LeetCode 120. 三角形最小路径和

约 6 分钟
文章信息 15 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 20-50 字节跳动 微软 美团 腾讯 百度 京东 华为 小米 亚马逊 面试经典 150 题
标签
数组 动态规划
目录

题目描述

✅ 120. 三角形最小路径和

image-20230311195934745

题意分析

给定一个三角形数组，第 i 行恰有 i + 1 个元素。从顶点出发，每一步只能从位置 (i, j) 走到下一行的 (i + 1, j) 或 (i + 1, j + 1)，一直走到最后一行，求路径上数字之和的最小值。

约束里行数不超过 200，元素总数约为 $n(n+1)/2$，两万出头，说明「把每个位置都算一遍」的代价完全可以接受，无需追求线性做法。

更重要的信号是元素可以为负。这意味着「每步都挑相邻两个数中较小的那个走」是不成立的：眼前多花一点，下一层可能换来一个很大的负数补回来，局部最优与全局最优没有关系，必须把所有位置的结果都算出来。

进阶要求只用 $O(n)$ 的额外空间，提示最终应该把二维的中间结果压成一行。

需要留意的边界情形：只有一行时答案就是那个元素本身；每行的长度不同，第 i 行的合法下标只有 0 ..= i；元素为负导致答案可能是负数，任何以 0 作为初值的写法都要格外小心。

解法：自底向上一维动态规划

核心思路

问题关键： 从每个位置都能走向下一行相邻的两个位置，直接枚举共有 $2^{n-1}$ 条路径；而多条路径会汇合到同一位置，之后的最优选择与如何到达这里无关，存在大量重复计算。

为什么选择自底向上 DP： 定义 f[i][j] 为从 (i, j) 走到底边的最小路径和，则两个后继总是存在，转移不需要处理行首、行尾的特殊情况。当前行只依赖下一行，还可以压缩成一维数组。

状态与转移： 处理第 i 行前，dp[j] 表示从下一行位置 (i+1, j) 出发的最小路径和。初始化 dp 为最后一行，然后按
dp[j] = triangle[i][j] + min(dp[j], dp[j+1])
从下往上更新。最终 dp[0] 就是从顶点出发的答案。

正确性： 最后一行没有后继，状态值就是元素本身，初始状态正确。假设 dp[j] 和 dp[j+1] 已分别是两个后继位置的最优值，那么当前位置的任何合法路径第一步只能走向二者之一，取较小值再加当前位置即可得到全部可能中的最优值。由自底向上的归纳，最后算出的 dp[0] 必然是全局最小路径和。

解题步骤

  1. 复制最后一行到 dp，作为 DP 边界。
  2. 从倒数第二行向上枚举到第 0 行。
  3. 第 i 行按 j = 0 .. i 正序更新 dp[j]。
  4. 返回 dp[0]。

口述示例： 对 [[2],[3,4],[6,5,7],[4,1,8,3]]，dp 依次为 [4,1,8,3] → [7,6,10] → [9,10] → [11]，答案为 11。

边界与反例： 只有一行时无需转移，直接返回该元素。不能每层贪心选较小的相邻数：[[1],[2,3],[100,100,1]] 中贪心会得到 103，而最优路径 1 → 3 → 1 的和是 5。

代码实现

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 dp[0];
    }
}

func minimumTotal(triangle [][]int) int {
    n := len(triangle)
    dp := append([]int(nil), triangle[n-1]...)

    for i := n - 2; i >= 0; i-- {
        for j := 0; j <= i; j++ {
            if dp[j+1] < dp[j] {
                dp[j] = dp[j+1]
            }
            dp[j] += triangle[i][j]
        }
    }
    return dp[0]
}

复杂度分析

  • 时间复杂度为 $O(n^2)$，等价于遍历三角形的全部 $n(n+1)/2$ 个位置一次。
  • 空间复杂度为 $O(n)$，一维数组保存下一行的状态；未压缩的二维 DP 需要 $O(n^2)$。

关键点总结

  • 状态要描述“从当前位置到底部的最优代价”，这样不同来路可以复用同一结果。
  • 自底向上的两个后继下标始终合法，比自顶向下少了两侧边界分支。
  • 一维压缩后必须正序更新：计算 dp[j] 时，dp[j] 与 dp[j+1] 都还是下一行的旧状态。
  • 如果还要输出具体路径，需要额外记录每个位置选择了哪个后继；本题只求最小和，不保存路径即可。

易错点总结

  • dp 初始化为 0 而不是最后一行：会漏掉底边的路径代价。
  • 内层范围写成整行数组长度而不是 0 .. i：会访问不存在的三角形元素。
  • 一维 DP 倒序更新：dp[j+1] 已被本轮覆盖，会把不同层的状态混在一起。
  • 返回整个 dp 的最小值：未使用的位置仍是旧状态，答案只能取 dp[0]。
  • 把局部较小的下一步当作全局最优：负数或后续大权重都能轻易构造反例。

相似题目

题目 难度 考察点
62. 不同路径 中等 求方案数而非最值，转移是相加；网格规整，还能直接用组合数公式一步算出
63. 不同路径 II 中等 在 62 题上加入障碍格，障碍处状态置 0，还要单独处理起点被堵的情况
64. 最小路径和 中等 矩形网格中只能右移或下移，首行首列没有两个来源，必须单独初始化，不像三角形那样有天然边界
174. 地下城游戏 困难 路径上带「血量不能归零」的过程约束，只能从终点倒推所需的最小初始值，正推会失效
688. 骑士在棋盘上的概率 中等 转移有八个方向且带概率权重，状态必须额外带上「剩余步数」这一维
931. 下降路径最小和 中等 矩形网格中每步可落到下一行的三个相邻列，起点不固定，答案取末行的最小值
1289. 下降路径最小和 II 困难 只禁止同列，朴素转移是 $O(n^3)$，需维护每行的最小与次小值才能降到 $O(n^2)$
1301. 最大得分的路径数目 困难 要同时求最大得分与达成该得分的方案数，两个状态必须一起转移并取模
1594. 矩阵的最大非负积 中等 负数相乘会翻号，最大值可能由最小值转化而来，需同时维护最大与最小两个状态
LCR 098. 不同路径 中等 62 题的镜像题，适合用来单独练习一维滚动数组的写法
LCR 099. 最小路径和 中等 64 题的镜像题，适合对照检查首行首列的初始化有没有写漏
LCR 100. 三角形最小路径和 中等 本题的镜像题，可用来验证自顶向下写法的两处边界特判是否完整
剑指 Offer 47. 礼物的最大价值 中等 求最大值而非最小值，转移方向与 64 题相同，但初值要设成 0 而不是极大值