LeetCode 120. 三角形最小路径和：动态规划详解

在LeetCode的动态规划题目中「三角形最小路径和」是一道经典的入门级题目它既考察了对动态规划核心思想的理解也需要我们结合题目特性设计合理的状态转移方程。今天就来一步步拆解这道题从题目分析到代码实现再到思路优化帮你彻底搞懂这道题的解题逻辑。一、题目回顾明确需求与约束题目给出一个三角形triangle要求找出自顶向下的最小路径和核心约束如下每一步只能移动到下一行中「相邻的结点」相邻结点定义当前行下标为i下一步可移动到下一行的i或i1下标三角形的行数不固定每一行的元素个数等于当前行的行号从0开始计数的话第0行1个元素第1行2个元素以此类推。举个简单示例若三角形为[[2],[3,4],[6,5,7],[4,1,8,3]]自顶向下的最小路径和为 2→3→5→1 11。二、解题思路为什么用动态规划这道题的核心是「求最小路径和」而路径的选择具有「重叠子问题」和「最优子结构」这正是动态规划的适用场景重叠子问题到达第i行第j个元素的最小路径和依赖于到达第i-1行第j个和第j-1个元素的最小路径和除了边界情况最优子结构到达第i行第j个元素的最小路径和是其上方两个可能路径的最小路径和加上当前元素的值即「局部最优推导全局最优」。因此我们可以用动态规划的思路通过构建一个DP数组逐步计算每一步的最小路径和最终得到整个三角形的最小路径和。三、代码逐行解析读懂每一步的意义先给出完整的解题代码题目要求的TypeScript版本再逐行拆解其逻辑functionminimumTotal(triangle:number[][]):number{constLentriangle.length;constdp:number[][]newArray(Len);for(leti0;iLen;i){dp[i]newArray(i1).fill(0);}dp[0][0]triangle[0][0];for(leti1;iLen;i){for(letj0;ji;j){if(j0){dp[i][j]dp[i-1][j]triangle[i][j];}elseif(ji){dp[i][j]dp[i-1][j-1]triangle[i][j];}else{dp[i][j]Math.min(dp[i-1][j],dp[i-1][j-1])triangle[i][j];}}}returnMath.min(...dp[Len-1]);};1. 初始化DP数组首先获取三角形的行数Len然后创建一个二维DP数组dp其中dp[i][j]表示「到达第i行第j个元素的最小路径和」。由于第i行有i1个元素行号从0开始所以我们通过循环给每一行的DP数组初始化长度为i1初始值填充为0。2. 边界条件三角形顶部三角形的顶部只有一个元素第0行第0列到达这个元素的路径只有一条所以dp[0][0] triangle[0][0]这是整个DP数组的起始值。3. 状态转移填充DP数组从第1行开始因为第0行已经初始化逐行逐列填充DP数组分三种情况讨论当j 0当前列是当前行的第一列只能从上层的第一列j0移动过来所以dp[i][j] dp[i-1][j] triangle[i][j]当j i当前列是当前行的最后一列只能从上层的最后一列j-1移动过来所以dp[i][j] dp[i-1][j-1] triangle[i][j]其他情况中间列可以从上层的j列或j-1列移动过来取两者的最小值再加上当前元素的值即dp[i][j] Math.min(dp[i-1][j], dp[i-1][j-1]) triangle[i][j]。4. 最终结果取最后一行的最小值DP数组填充完成后最后一行的每个元素dp[Len-1][j]分别表示到达三角形底部每一个元素的最小路径和。我们只需要取这一行的最小值就是整个三角形的最小路径和用Math.min(...dp[Len-1])即可实现。四、代码测试验证逻辑正确性用前面提到的示例triangle [[2],[3,4],[6,5,7],[4,1,8,3]]测试代码初始化DP数组为[[0], [0,0], [0,0,0], [0,0,0,0]]设置dp[0][0] 2第1行i1j0 → dp[1][0] 235j1 → dp[1][1] 246第2行i2j0 → 5611j1 → min(5,6)510j2 → 6713第3行i3j0 → 11415j1 → min(11,10)111j2 → min(10,13)818j3 →13316最后一行最小值为 11与预期结果一致代码正确。五、优化方向空间复杂度优化上面的代码空间复杂度是O(n²)n为三角形行数因为我们创建了一个和三角形大小一致的DP数组。但实际上我们可以优化到O(n)核心思路是「滚动数组」观察状态转移方程我们发现第i行的DP值只依赖于第i-1行的DP值因此不需要保存整个二维数组只需要一个一维数组不断覆盖更新即可。优化后的代码TypeScriptfunctionminimumTotal(triangle:number[][]):number{constLentriangle.length;letdp:number[]newArray(Len).fill(0);dp[0]triangle[0][0];for(leti1;iLen;i){// 从后往前更新避免覆盖上一行未使用的值for(letji;j0;j--){if(j0){dp[j]dp[j]triangle[i][j];}elseif(ji){dp[j]dp[j-1]triangle[i][j];}else{dp[j]Math.min(dp[j],dp[j-1])triangle[i][j];}}}returnMath.min(...dp);};注意优化后需要「从后往前」更新一维数组因为如果从前往后更新会覆盖上一行的dp[j-1]导致后续计算出错。六、总结解题关键与易错点解题关键明确DP数组的定义dp[i][j]表示到达第i行第j个元素的最小路径和区分边界情况第一列和最后一列和中间情况正确写出状态转移方程最终结果是最后一行的最小值。易错点忽略边界条件忘记第一列只能从上层第一列过来最后一列只能从上层最后一列过来DP数组初始化错误第i行的长度应该是i1而非固定长度空间优化时从前往后更新一维数组导致数据覆盖出错。这道题虽然简单但却是动态规划思想的典型应用掌握它的解题逻辑能为后续解决更复杂的DP问题打下基础。