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

约 4 分钟
文章信息 5 个分类 3 个标签
分类
LeetCode 中等 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
数组 动态规划 LCR

题目描述

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

image-20260929004345387

image-20260929004345388

题意分析

三角形第 i 行有 i + 1 个元素。从 (i, j) 只能走到下一行的 (i + 1, j) 或 (i + 1, j + 1)，求从顶点走到底行的最小路径和。

元素可以为负，路径仍必须走到底行，不能提前停止。进阶要求只用 $O(n)$ 额外空间，其中 $n$ 是行数。

解法：自底向上的三角形 DP

核心思路

[!blue]

定义 f[i][j] 为从 (i, j) 出发走到底行的最小路径和。下一步只有两个合法位置，先选择它们较小的完整后续代价，再加上当前值，即 f[i][j] = triangle[i][j] + min(f[i + 1][j], f[i + 1][j + 1])。比较的是后续整条路径的代价，不能只挑下一行眼前较小的数字。

最后一行已经是终点，所以它的状态就是格子自身的值。由底向上处理时，第 i + 1 行比第 i 行多一个元素，当前每个合法 j 的两个后继 j、j + 1 都存在，无需分别处理行首和行尾。

每行只依赖下一行，用长度为 n 的 dp 复制最后一行作为初值即可。从倒数第二行向上处理时，内层让 j 从 0 递增到 i：赋值前，dp[j] 和右侧的 dp[j + 1] 都尚未在本轮覆盖，仍是下一行的结果；把两者的较小值加当前值，写回 dp[j]。

处理完一行后，dp[0..i] 保存这一行的状态，更右侧的遗留值不再是后续所需范围。最终只有 dp[0] 表示从顶点出发的答案。初始化和转移都使用真实路径代价，不依赖非负性，因此负数也能正常参与比较。

解题步骤

  1. 创建长度为 n 的数组，复制三角形最后一行。
  2. 从 i = n - 2 递减到 0，逐行向上处理。
  3. 每行从 j = 0 到 i，将当前值加上 min(dp[j], dp[j + 1]) 后写回。
  4. 返回 dp[0]；只有一行时，外层循环自然跳过。

代码实现

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)$，初始化和转移合计处理三角形的 $n(n+1)/2$ 个元素。
  • 空间复杂度：$O(n)$，只保存一行状态，且不修改输入三角形。

关键点总结

[!green]

  • 状态是从当前格子到底行的完整最小和，答案位于顶点，而不是底行最小值。
  • 滚动方向取决于需要读取旧状态还是新状态；本题两项都需下一行旧值，正序能保留右侧旧值。
  • 最后一行必须计入路径，单行输入的答案就是该元素本身。

易错点总结

[!yellow]

  • 本实现从倒数第二行开始转移，若将初始 dp 全置 0，就会漏掉最后一行的代价。
  • dp 长度应为 n，每行却只能处理 j <= i，不能把整行缓冲区都当成当前三角形行。
  • 内层倒序会使 dp[j + 1] 已变成本行值，混淆相邻两层。
  • 结束后不能取整个 dp 的最小值，除 dp[0] 外的值只是下面各行遗留的状态。

相似题目

题目 难度 关联与区别
64. 最小路径和 中等 同样把每层最优结果传给下一层，本题相邻行长度不同且只能走到相邻两个位置。
931. 下降路径最小和 中等 同样是自上而下的最小下降路径，原题每格可选下方三个位置。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/75190715
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！