LeetCode 120题三角形最小路径和最优解法：动态规划详解与代码实现

一、题目解读

LeetCode 120题“三角形最小路径和”要求给定一个由数字组成的三角形，从顶部开始向下移动，每次可向左或向右移动一格，计算从顶至底的最小路径和。三角形以二维向量形式给出，每层元素数量递增，需找到所有可行路径中的最小值。该问题属于经典的动态规划应用场景，需通过合理设计状态转移方程来求解。

二、解题思路

采用动态规划策略，核心思想是自底向上递推。从三角形倒数第二层开始，逐层向上计算每个节点的最小路径和。关键在于利用下一层相邻节点的最小值，通过状态转移方程更新当前节点的值，最终得到顶点的最小路径和。该解法避免了暴力枚举所有路径，时间复杂度优化至O(n^2)（n为层数）。

三、解题步骤

1. 初始化：获取三角形层数n，确定递推起点为倒数第二层（i=n-2）。

2. 外层循环：从n-2到0层，逐层向上递推。

3. 内层循环：遍历当前层每个节点（0≤j≤i）。

4. 状态转移：当前节点的最小路径和 = 当前值 + 下一层相邻两个节点的较小值（即min(triangle[i+1][j], triangle[i+1][j+1])）。

5. 结果返回：最终顶层节点triangle[0][0]即为最小路径和。

四、代码与注释

#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];  // 返回顶点的最小路径和
    }
};

代码特点：

● 原地修改三角形数组，节省空间复杂度（O(1)）。

● 利用min函数简化相邻节点比较，提升代码可读性。

五、总结

动态规划是解决此类路径优化问题的关键，需明确状态定义（每层节点的最小路径和）与转移方程。自底向上的递推方式避免了递归开销，且通过原地修改数组进一步优化资源消耗。在实际应用中，该思路可扩展至其他图形路径问题，为算法设计提供通用框架。