LeetCode 120. 三角形最小路径和

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

题目描述

✅ 120. 三角形最小路径和

image-20260928201355088

image-20260928201355089

题意分析

从三角形顶部走到最后一行，每一层必须选一个节点并累加其值。位于第 i 行第 j 列时，下一步只能到第 i + 1 行的第 j 列或第 j + 1 列，求所有完整路径中的最小总和。

节点值可能为负数，不能只根据眼前两个孩子谁更小作决定，必须考虑后续路径的总代价。题目只要求最小和，不要求返回路径，并要求尝试把额外空间控制在三角形行数的线性规模。

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

核心思路

[!blue]

定义 cost[i][j] 为从位置 (i, j) 出发一直到底部的最小路径和，包含当前位置的值。任何完整路径下一步只可能进入下方的两个相邻位置，因此它的最优后续代价为这两个子问题的较小值：cost[i][j] = triangle[i][j] + min(cost[i + 1][j], cost[i + 1][j + 1])。比较的是两条完整后续路径，而不是两个孩子的单个数值。

最后一行已经到达终点，从某个位置出发的代价就是该位置本身，所以先复制底边作为初始状态。再从倒数第二行向上计算；当需要求某一行时，它依赖的下一行已经全部求好，正好符合递推顺序。

当前行只依赖下一行，可以复用一维数组 dp。更新第 j 列时，dp[j]、dp[j + 1] 必须仍是下一行的两个旧状态，因此列下标从左向右推进：已经覆盖的只有 j 左边的位置，不会碰到当前需要的两个值。

处理完第 i 行后，dp 的前 i + 1 个位置表示该行结果，后面的旧值不属于这一行，不再参与答案选择。最终第 0 行只有顶点，对应 dp[0]，它就是从唯一合法起点出发的最小和；不能对整个缓冲数组再取最小值。底边被复制，输入三角形不会被覆盖。

解题步骤

  1. 设三角形有 n 行，将最后一行复制到长度为 n 的 dp。
  2. 从第 n - 2 行向上处理到第 0 行。
  3. 对当前第 i 行，按 j = 0 到 i 的顺序，将当前位置值加上 dp[j] 和 dp[j + 1] 的较小值，写回 dp[j]。
  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] = 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(n + 1)/2$。
  • 空间复杂度：$O(n)$，只保存长度为底边宽度的一行状态，满足题目进阶要求。

关键点总结

[!green]

  • 状态表示“从当前点到底部”的总代价，转移比较两种完整后续选择。
  • 自底向上计算时，两种后继都存在，不需要为三角形两侧单独补前驱。
  • 一维更新从左到右，保证读到下一行的两个旧状态。
  • 每处理一行，有效状态范围缩短一格，最后只有 dp[0] 是顶点答案。

易错点总结

[!yellow]

  • 用全零数组替代底边初始化，却仍从倒数第二行开始，会漏算底边代价。
  • 内层遍历整个缓冲数组，而不是当前行的 0 到 i，会访问不存在的三角形元素。
  • 从右向左更新，右邻状态已经来自本行，会把不同层的代价混在一起。
  • 返回缓冲数组所有位置的最小值，会把不对应顶点的旧状态当成答案。
  • 只贪心选择当前较小的孩子，没有比较后续完整代价，不能保证全局最小路径和。

相似题目

题目 难度 关联与区别
64. 最小路径和 中等 同样把每层最优结果传给下一层，本题相邻行长度不同且只能走到相邻两个位置。
931. 下降路径最小和 中等 同样是自上而下的最小下降路径，原题每格可选下方三个位置。
62. 不同路径 中等 在网格上从前驱状态递推路径；本题按三角形相邻位置求最小路径，该题累加向右向下的路径数。
63. 不同路径 II 中等 在网格上从前驱状态递推路径；本题按三角形相邻位置求最小路径，该题遇障碍时清零可达路径。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/50708487
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！