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

Categories:

题目描述
思路分析
1. 解法一：自底向上 DP（空间优化，推荐）
2. 解法二：原地自底向上 DP
相似题目

题目描述

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

思路分析

解法一：自底向上 DP（空间优化，推荐）

核心思路：

用一维数组 dp 初始化为三角形最后一行，从倒数第二行开始向上逐层更新。

对第 i 行第 j 列，状态转移方程为：dp[j] = triangle[i][j] + min(dp[j], dp[j+1])，即当前位置的值加上下一行相邻两位置的较小值。

每层从左到右原地更新，最终 dp[0] 即为从顶到底的最小路径和。

无需二维 DP 表，空间压缩至 O(n)。

复杂度分析：

时间复杂度：O(n²)，其中 n 表示三角形的行数，每个元素恰好被遍历一次。

空间复杂度：O(n)，其中 n 表示三角形最后一行的元素个数，使用一维 DP 数组。

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        // 初始化 dp 为最后一行
        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 为最后一行
    dp := make([]int, n)
    copy(dp, triangle[n-1])
    // 从倒数第二行向上遍历
    for i := n - 2; i >= 0; i-- {
        for j := 0; j <= i; j++ {
            // 当前位置 = 当前值 + 下一行相邻两位置的较小值
            dp[j] = triangle[i][j] + min(dp[j], dp[j+1])
        }
    }
    return dp[0]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

解法二：原地自底向上 DP

核心思路：

直接在原始三角形数组上进行修改，省去额外 DP 数组。

从倒数第二行开始向上，对每个位置 (i, j) 执行：triangle[i][j] += min(triangle[i+1][j], triangle[i+1][j+1])。

最终 triangle[0][0] 即为答案。注意此方法会修改输入数据。

复杂度分析：

时间复杂度：O(n²)，其中 n 表示三角形的行数。

空间复杂度：O(1)，原地修改输入数组，不使用额外空间。

class Solution {
    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 minBelow = 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) + minBelow);
            }
        }
        return triangle.get(0).get(0);
    }
}

func minimumTotal(triangle [][]int) int {
    n := len(triangle)
    // 从倒数第二行开始向上原地修改
    for i := n - 2; i >= 0; i-- {
        for j := 0; j <= i; j++ {
            // 原地更新为当前值加上下方相邻两格的较小值
            triangle[i][j] += min(triangle[i+1][j], triangle[i+1][j+1])
        }
    }
    return triangle[0][0]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

相似题目

题目	难度	考察点
64. 最小路径和	中等	动态规划 / 网格路径
62. 不同路径	中等	动态规划 / 路径计数
63. 不同路径 II	中等	动态规划 / 障碍物
931. 下降路径最小和	中等	动态规划 / 自顶向下
1289. 下降路径最小和 II	困难	动态规划 / 优化选取
746. 使用最小花费爬楼梯	简单	动态规划 / 线性路径

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/75190715