LeetCode LCR 100. 三角形最小路径和

2026-03-28 HGNULB 约 9 分钟

文章信息 5 个分类 3 个标签

分类

LeetCode 中等 119 经典题变种挑战剑指 Offer 剑指 Offer（专项突击版）

题目描述

✅ LCR 100. 三角形最小路径和

题意分析

给定一个三角形数组，第 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}$ 条路径，$n = 200$ 时完全不可能跑完。

瓶颈在于大量重复计算：不同的路径在中途会汇合到同一个位置，而一旦汇合，它们后续能走的路和产生的代价就完全相同了，却被反复展开了无数遍。

关键观察正是这一点——从位置 (i, j) 往下走的最优代价只取决于 (i, j) 本身，与它上面是怎么走过来的无关。于是可以给每个位置定义一个与来路无关的量。

状态定义（自底向上）：f[i][j] 表示从位置 (i, j) 出发，走到最后一行所能得到的最小路径和。

转移方程：f[i][j] = triangle[i][j] + min(f[i + 1][j], f[i + 1][j + 1])。

边界：f[n - 1][j] = triangle[n - 1][j]，即最后一行自身就是终点。答案是 f[0][0]。

之所以选自底向上而不是自顶向下，是因为边界落在了「天然完整」的一侧：第 i 行的下标范围是 0 ..= i，而第 i + 1 行的下标范围是 0 ..= i + 1，所以转移里用到的 j 与 j + 1 必然都存在，一个越界判断都不需要。反过来自顶向下时，第 i 行的行首没有左上邻居、行尾没有右上邻居，必须写两处特判，代码更长也更容易出错。

空间压缩：f[i][*] 只依赖 f[i + 1][*]，用一维数组 dp[j] 滚动即可，dp 始终保存「下一行」的结果。因为计算 dp[j] 时只读 dp[j] 和 dp[j + 1]，而 j 从小到大遍历时右侧的 dp[j + 1] 尚未被本行覆盖，就地写回是安全的。

解题步骤

开一个长度为 n 的数组 dp，用最后一行的数字初始化。原因是它既是转移的边界，也是滚动数组的初始状态；长度取 n 而不是当前行长度，是为了让后续读 dp[j + 1] 始终合法。

从 i = n - 2 开始，逐行向上枚举。原因是每一行都依赖下一行的结果，必须自底向上推进。

内层 j 从 0 到 i，正好覆盖第 i 行的全部合法下标。原因是第 i 行只有 i + 1 个元素，多算的位置会污染上一层。

每个位置取 min(dp[j], dp[j + 1]) 再加上 triangle[i][j]，就地写回 dp[j]。原因是这两个格子正是它在下一行能到达的两个位置，此刻它们保存的还是下一行的值。

内层循环必须正序（j 递增）。原因是本行写 dp[j] 之后还要读 dp[j + 1]，正序时被读的格子还没被覆盖；若倒序，dp[j + 1] 已是本行的值，转移就串层了。

全部处理完后返回 dp[0]。原因是它对应 f[0][0]，即从顶点出发的最小路径和。

以 triangle = [[2],[3,4],[6,5,7],[4,1,8,3]] 走一遍：初始化 dp = [4, 1, 8, 3]（最后一行）。

处理第 2 行 [6,5,7]：j = 0 时 6 + min(dp[0]=4, dp[1]=1) = 6 + 1 = 7；j = 1 时 5 + min(dp[1]=1, dp[2]=8) = 5 + 1 = 6；j = 2 时 7 + min(dp[2]=8, dp[3]=3) = 7 + 3 = 10。此时 dp = [7, 6, 10, 3]，末位 3 是遗留的旧值，不会再被读到。

处理第 1 行 [3,4]：j = 0 时 3 + min(7, 6) = 9；j = 1 时 4 + min(6, 10) = 10。此时 dp = [9, 10, 10, 3]。

处理第 0 行 [2]：j = 0 时 2 + min(9, 10) = 11。此时 dp = [11, 10, 10, 3]。

返回 dp[0] = 11，对应的路径是 2 → 3 → 5 → 1。

代码实现

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] 和 dp[j + 1] 是当前位置下一行能到达的两个选择。
                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 := make([]int, n)
    for j := 0; j < n; j++ {
        dp[j] = triangle[n-1][j]
    }

    for i := n - 2; i >= 0; i-- {
        for j := 0; j <= i; j++ {
            // 从底向上更新，避免覆盖仍需要的状态。
            if dp[j] < dp[j+1] {
                dp[j] = triangle[i][j] + dp[j]
            } else {
                dp[j] = triangle[i][j] + dp[j+1]
            }
        }
    }
    return dp[0]
}

复杂度分析

时间复杂度：$O(n^2)$。外层从倒数第二行枚举到第 0 行共 $n - 1$ 轮，第 i 行做 i + 1 次转移，累计 $n(n+1)/2$ 次；每次转移只有一次比较和一次加法，是常数时间。主导项就是三角形的元素总数，等于说每个位置恰好被计算一次，相比 $2^{n-1}$ 条路径的枚举，省下的全是汇合后的重复展开。

空间复杂度：$O(n)$。只用一个长度为 $n$ 的一维数组，逐行就地覆盖，不随处理进度增长；未压缩的二维表是 $O(n^2)$。写成迭代而非递归，也不产生 $O(n)$ 的调用栈。

关键点总结

当「从某个位置往后的代价只取决于该位置本身」时，就应该给位置定义状态、让汇合的路径共用一次计算，而不是枚举路径；判断依据是「后续行为与来路无关」这一条。

状态定义的推进方向是可选的，优先选让边界落在天然完整一侧的方向。本题自底向上时底行直接就是初值、转移永不越界，省掉了自顶向下必须写的两处行首行尾特判。

一维滚动数组的遍历方向由「被覆盖的格子是否还会被本轮读到」决定：本题转移读 dp[j] 与 dp[j + 1]，正序安全；若转移读的是 dp[j - 1]，就必须倒序。写之前先问一句「我要读的格子写过了吗」。

只要元素可能为负，任何「每步选局部较优」的策略都不成立，必须把全部位置算完再取结论；看到负数约束就该立刻放弃逐步择优的想法。

面试视角：先把状态定义、转移方程、边界初值、答案位置这四件事完整说出来再动手写代码，然后主动提出把 $O(n^2)$ 的表压成 $O(n)$ 的滚动数组，正好回应题目的进阶要求。常见追问有：「为什么自底向上不需要特判」「一维数组为什么可以正序就地覆盖」「如果还要输出具体路径怎么办」（需额外记录每个位置选了哪一侧，或保留二维表回溯一遍）。

易错点总结

dp 初始化为全 0 而不是最后一行：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]] → 底行的数字被完全丢弃，算出 10 而不是 11。

dp 数组长度开成 n - 1：同样的四行三角形 → 初始化最后一行时写 dp[3] 就抛出数组越界异常。

内层循环写成 j < n：同样的用例 → 处理第 0 行时会去访问 triangle[0][1]，而该行只有一个元素，抛出越界异常；即使侥幸不越界，也会把不属于该行的位置算进 dp，污染上一层的结果。

内层循环倒序遍历 j：同样的用例 → 写 dp[j] 后再读 dp[j + 1] 时读到的已是本行的值，层次串位，最终返回 12 而不是 11。

改成自顶向下却不对行首行尾特判：任意行数大于 1 的三角形 → 第 i 行的 j = 0 没有左上邻居、j = i 没有右上邻居，读到不存在的下标而越界，或读到上一轮遗留的脏值。

每步只跟着相邻两数中较小的那个走：triangle = [[1],[2,3],[100,100,1]] → 从 1 走到 2 再被迫走 100，得到 103；正确答案是走 1 → 3 → 1 得到 5。

返回 dp 数组的最小值而不是 dp[0]：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]] → 结束时 dp = [11, 10, 10, 3]，后三位是下面几行遗留的旧值，取最小会返回 3。

对只有一行的输入额外补一次转移或返回 dp 的其他位置：triangle = [[-10]] → 外层循环本就从 i = -1 开始、一次都不执行，dp[0] 已是答案 -10；多做一步会越界，返回其他位置则得到 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 题的镜像题，适合对照检查首行首列的初始化有没有写漏
剑指 Offer 47. 礼物的最大价值	中等	求最大值而非最小值，转移方向与 64 题相同，但初值要设成 0 而不是极大值