LeetCode 120题三角形最小路径和最优解法：动态规划详解与代码实现
15小时前
一、题目解读
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函数简化相邻节点比较，提升代码可读性。
五、总结
动态规划是解决此类路径优化问题的关键，需明确状态定义（每层节点的最小路径和）与转移方程。自底向上的递推方式避免了递归开销，且通过原地修改数组进一步优化资源消耗。在实际应用中，该思路可扩展至其他图形路径问题，为算法设计提供通用框架。
原创内容 转载请注明出处
