01、三角形最小路径和

今天继续来说一下另外一个经典题目，三角形的最小路径和

https://leetcode.cn/problems/triangle/

题目描述

给定一个三角形 triangle，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点在这里指的是下标与上一层结点下标相同或者等于上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i****，那么下一步可以移动到下一行的下标 i 或 i + 1。

示例 1:

输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
   2
  3 4
 6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

不知道，大家此时有没有感觉，这个题目有点熟悉，好像做过类似的？

示例 2:

输入：triangle = [[-10]]
输出：-10

约束条件:

• 1 <= triangle.length <= 200
• triangle[0].length == 1
• triangle[i].length == triangle[i - 1].length + 1
• -10^4 <= triangle[i][j] <= 10^4

三角形移动规则

移动规则

三角形：
     2        (0,0)
    3 4       (1,0) (1,1)
   6 5 7      (2,0) (2,1) (2,2)
  4 1 8 3     (3,0) (3,1) (3,2) (3,3)

从 (i, j) 可以移动到：
1. (i+1, j) - 下一行同列
2. (i+1, j+1) - 下一行右一列

注意：只能向下走，不能横向或向上

动态规划解法⭐

DP 思路

dp[i][j] 表示从顶部到 (i, j) 的最小路径和

状态转移：
dp[i][j] = triangle[i][j] + min(dp[i-1][j-1], dp[i-1][j])

注意边界：
- 最左边：只能从正上方来
- 最右边：只能从左上方来

看到这，我们彻底想起来了，这种题目，我可太熟悉了啊，之前做过最小路径和，是不是思路一致呢？

代码实现

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        vector<vector<int>> dp(n, vector<int>(n, INT_MAX));

        // 初始化顶点
        dp[0][0] = triangle[0][0];

        // 填充 dp 数组
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                if (j == 0) {
                    // 最左边：只能从正上方来
                    dp[i][j] = dp[i-1][j] + triangle[i][j];
                } else if (j == i) {
                    // 最右边：只能从左上方来
                    dp[i][j] = dp[i-1][j-1] + triangle[i][j];
                } else {
                    // 中间：从左上或正上来，取较小值
                    dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j];
                }
            }
        }

        // 返回最后一行的最小值
        return *min_element(dp[n-1].begin(), dp[n-1].end());
    }
};

时间复杂度: O(n²)

空间复杂度: O(n²)

空间优化⭐⭐

一维DP（自顶向下优化版）

核心思想

从二维优化到一维的关键观察：

二维 DP 分析：
dp[i][j] = triangle[i][j] + min(dp[i-1][j-1], dp[i-1][j])

关键发现：
- 第 i 行的 dp 值只依赖于第 i-1 行
- 不需要保存所有行的历史数据
- 可以用一维数组滚动更新

优化策略：
用一个长度为 n 的一维数组 dp
- dp[j] 表示到达当前行第 j 列的最小路径和
- 处理新的一行时，复用同一个 dp 数组

详细图解示例

以 triangle = [[2],[3,4],[6,5,7],[4,1,8,3]] 为例：

代码实现

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();

        // dp[j] 表示到达当前行第 j 列的最小路径和
        vector<int> dp(n);

        // 初始化：起点
        dp[0] = triangle[0][0];

        // 从第 1 行开始处理
        for (int i = 1; i < n; i++) {
            // 关键：从右往左更新（避免覆盖未使用的旧值）
            for (int j = i; j >= 0; j--) {
                if (j == i) {
                    // 最右边元素，只能从左上方来
                    // 当前行的最右边 = 上一行的最右边 + 当前值
                    dp[j] = dp[j-1] + triangle[i][j];
                }
                else if (j == 0) {
                    // 最左边元素，只能从正上方来
                    // dp[0] 保持原位置，只加当前值
                    dp[j] = dp[j] + triangle[i][j];
                }
                else {
                    // 中间元素，可以从左上或正上来
                    // 此时 dp[j-1] 还是旧值（上一行的），dp[j] 也是旧值
                    dp[j] = min(dp[j-1], dp[j]) + triangle[i][j];
                }
            }
        }

        // 返回最后一行的最小值
        return *min_element(dp.begin(), dp.end());
    }
}

时间复杂度: O(n²) - 遍历三角形的所有元素

空间复杂度: O(n) - 只需要一个长度为 n 的数组