力扣120题终极攻略:动态规划解三角形最小路径和(C++实现)

截图未命名 一、问题描述 给定一个三角形 triangle ,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的节点上。 二、​​C++​​解决方案(带注释)

#include <vector>
#include <algorithm>
using namespACe std;

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        // 从倒数第二层开始向上递推
        for (int i = n - 2; i >= 0; --i) {
            for (int j = 0; j <= i; ++j) {
                // 当前节点的最小路径和 = 当前值 + 下一层相邻两个节点的较小值
                triangle[i][j] += min(triangle[i+1][j], triangle[i+1][j+1]);
            }
        }
        return triangle[0][0]; // 返回顶点的最小路径和
    }
};

三、​​算法​​解析

  1. ​动态规划​思想:采用自底向上的方法,避免重复计算
  2. ​时间复杂度​:O(n²),其中n是三角形的行数
  3. 空间复杂度:O(1),直接在原数组上修改

四、​​优化​​思路

  1. 可以使用一维数组进一步优化空间复杂度
  2. ​​边界条件处理​​:当三角形为空时直接返回0

转自:力扣120题终极攻略:动态规划解三角形最小路径和(C++实现)

评论

暂无评论