Triangle

120. 三角形最小路径和

分析

状态定义：triangle[i][j] 表示从底层到第i行j列节点的最小路径和
状态转移：triangle[i][j] 的值等于下一层相邻节点中的较小值 + 当前节点值: triangle[i][j] += std::min(triangle[i + 1][j], triangle[i + 1][j + 1])
最终，triangle[0][0] 中存储的就是从底端到顶端的最小路径和

时间复杂度

时间复杂度 O(n^2)，其中 n 是三角形的行数。每一行最多有 n 个元素，处理每个元素时需要计算两个相邻节点的最小值

空间复杂度

空间复杂度为 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


class Solution
{
public:
    int minimumTotal(vector<vector<int>>& triangle)
    {
        // 从倒数第二行开始，向上更新最小路径和
        for (int i = triangle.size() - 2; i >= 0; --i)
            for (int j = 0; j < triangle[i].size(); ++j)  // 遍历每一行的元素
                triangle[i][j] += std::min(triangle[i + 1][j], triangle[i + 1][j + 1]);  // 更新当前点的最小路径和
        return triangle[0][0];  // 返回到达顶点的最小路径和
    }
};