力扣经典题目之120.三角形最小路径和

今天继续给大家分享一道力扣的做题心得今天这道题目是 120.三角形最小路径和

题目如下：

题目链接：三角形最小路径和

1，题目分析

        这个问题要求我们在一个数字三角形中找到从顶部到底部的路径，使得路径上的数字总和最小。三角形的每一行数字数量递增，从顶部开始，每一步可以选择移动到下一行的相邻数字上。对于这类问题是一种经典的动态规划的问题，我们使用动态规划的相关方法解决此题。

        动态规划（Dynamic Programming, DP）是一种通过把原问题分解为相对简单的子问题的方式来求解复杂问题的方法。在这个问题中，我们使用DP来存储到达每个位置的最小路径和。

2，解题思路

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[][] dp = new int[n][n];
        
        dp[0][0] = triangle.get(0).get(0);
        
        for (int i = 1; i < n; i++) {
            dp[i][0] = dp[i-1][0] + triangle.get(i).get(0);
        }
        
        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= i; j++) {
                if (j == i) {
                    // 处理每一行的最后一个元素
                    dp[i][j] = dp[i-1][j-1] + triangle.get(i).get(j);
                } else {
                    // 处理中间元素
                    dp[i][j] = Math.min(dp[i-1][j-1], dp[i-1][j]) + triangle.get(i).get(j);
                }
            }
        }
        // 找最后一行的最小值
        int minPathSum = dp[n-1][0];
        for (int j = 1; j < n; j++) {
            if (dp[n-1][j] < minPathSum) {
                minPathSum = dp[n-1][j];
            }
        }
        
        return minPathSum;
    }
}

1. 初始化DP数组：创建一个二维数组dp，其中dp[i][j]表示到达第i行第j列位置的最小路径和。初始时，dp[0][0]被设置为三角形顶部的数字。
2. 边界条件处理：
   • 对于每一行的第一个元素，由于只能从上一行的第一个元素到达，因此dp[i][0] = dp[i-1][0] + triangle.get(i).get(0)。
   • 对于每一行的最后一个元素，由于只能从上一行的最后一个元素到达，因此dp[i][i] = dp[i-1][i-1] + triangle.get(i).get(i)。
3. 填充DP数组：
   • 对于中间的元素，我们可以从上一行的两个相邻元素到达，因此需要选择路径和较小的那个，即dp[i][j] = Math.min(dp[i-1][j-1], dp[i-1][j]) + triangle.get(i).get(j)。

4. 结果提取：遍历dp数组的最后一行，找到最小值，这个值就是从三角形顶部到底部的最小路径和

代码详细分析 

1. 初始化动态规划数组

int n = triangle.size();
int[][] dp = new int[n][n];

这里创建了一个二维数组 dp，其大小与输入的三角形相同。dp[i][j] 用于存储从三角形顶部到位置 (i, j) 的最小路径和。

2. 初始化第一个元素

dp[0][0] = triangle.get(0).get(0);

三角形的顶部元素直接赋值给 dp[0][0]，因为这是路径的起点。

3. 初始化第一列

for (int i = 1; i < n; i++) {
    dp[i][0] = dp[i-1][0] + triangle.get(i).get(0);
}

对于每一行的第一个元素，只能从上一行的第一个元素移动过来，因此直接累加即可。

4. 填充动态规划数组

for (int i = 1; i < n; i++) {
    for (int j = 1; j <= i; j++) {
        if (j == i) {
            // 处理每一行的最后一个元素
            dp[i][j] = dp[i-1][j-1] + triangle.get(i).get(j);
        } else {
            // 处理中间元素
            dp[i][j] = Math.min(dp[i-1][j-1], dp[i-1][j]) + triangle.get(i).get(j);
        }
    }
}

• 对于每一行的最后一个元素，只能从上一行的最后一个元素移动过来，因此直接累加。
• 对于中间的元素，可以选择从上一行的相邻两个元素中路径和较小的那个移动过来，因此取两者的最小值并累加。

5. 找到最后一行的最小值

int minPathSum = dp[n-1][0];
for (int j = 1; j < n; j++) {
    if (dp[n-1][j] < minPathSum) {
        minPathSum = dp[n-1][j];
    }
}

最后一行的每个元素代表从顶部到该位置的最小路径和。遍历最后一行，找到其中的最小值，即为整个三角形的最小路径和。

6. 返回结果

return minPathSum;

返回计算得到的最小路径和。

4，总结

        感谢大家的阅读，希望这篇解题心得能为大家带来一些收获，我们共同进步！大家的点赞就是我的动力谢谢大家，还有什么更优解或者问题欢迎大家在评论区讨论分享！