题目

给定一个三角形 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

解题思路

解决这个问题的关键在于，任何一条从顶部到底部的路径，它到达某一个节点 (i, j)（第 i 行，第 j 列）的路径和，都必然包含了到达它上一层相邻节点的最小路径和。

这符合动态规划的两个核心特征：

最优子结构：问题的最优解包含了其子问题的最优解。也就是说，要计算到 (i, j) 的最小路径和，我们只需要知道到它上一层 (i-1, j-1) 和 (i-1, j) 的最小路径和。
重叠子问题：在计算过程中，很多子问题的解会被重复计算。例如，计算到第 i 行的路径会多次用到第 i-1 行的计算结果。

自顶向下动态规划 (Top-Down DP)

这是最直观的思路，我们从三角形的顶端开始，逐层向下计算。

1. 定义状态

我们定义一个二维数组 dp[i][j]，它表示从三角形顶部 (0, 0) 到达节点 (i, j) 的最小路径和。

2. 状态转移方程

要想到达 (i, j) 这个节点，只能从它正上方的 (i-1, j) 或者左上方的 (i-1, j-1) 走过来。因此，到达 (i, j) 的最小路径和，就是 (i, j) 自身的值，加上到达它两个父节点的最小路径和中的较小者。

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

我们还需要考虑边界情况：

最左侧的边 (j = 0)：它只能从正上方 (i-1, 0) 过来。 dp[i][0] = triangle[i][0] + dp[i-1][0]
最右侧的边 (j = i)：它只能从左上方 (i-1, i-1) 过来。 dp[i][i] = triangle[i][i] + dp[i-1][i-1]

3. 初始状态

dp[0][0] = triangle[0][0]

4. 最终结果

当我们计算完所有 dp 值后，最小总路径和就是 dp 数组最后一行的所有值中的最小值。 result = min(dp[n-1][0], dp[n-1][1], ..., dp[n-1][n-1])，其中 n 是三角形的行数。

复杂度分析

时间复杂度: O(n^2)，其中 n 是三角形的行数。因为需要遍历三角形中的每一个元素一次。
空间复杂度: O(1) (不计算输入数据本身占用的空间)。因为可以在原始数组上直接修改，没有使用任何额外的、随输入规模 n 增长的存储空间。

具体代码

自顶向下的代码

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {

        const int row = triangle.size();

        if(row == 1)
            return triangle[0][0];

        // 下一行选上一行左右的更小数字累加
        for(int i = 1; i < row; i++)
        {
            for(int j = 0; j <= i; j++)
            {
                if(j == 0) // 下一行第一个数字只能读取右上的数字
                    triangle[i][j] += triangle[i - 1][j];
                else if(j == i) // 下一行最后一个数字只能读取左上的数字
                    triangle[i][j] += triangle[i - 1][j - 1];
                else
                    triangle[i][j] += min(triangle[i - 1][j - 1], triangle[i - 1][j]);
            }
        }

        return *min_element(triangle.back().begin(), triangle.back().end());
        
    }
};

优化：自底向上的代码

这个方法不用if else的判断

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        if (triangle.empty()) {
            return 0;
        }

        int row = triangle.size();

        // 从倒数第二行开始向上遍历
        for (int i = row - 2; i >= 0; --i) {
            // 遍历当前行的所有元素
            for (int j = 0; j < triangle[i].size(); ++j) {
                // 更新当前元素的值，内层循环不再需要 if/else 判断
                triangle[i][j] += min(triangle[i + 1][j], triangle[i + 1][j + 1]);
            }
        }

        // 最终结果就存储在三角形的顶端
        return triangle[0][0];
    }
};

收起

120. 三角形最小路径和

beautifulremi

题目