LeetCode题练习与总结：三角形最小路径和--120

一、题目描述

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

示例 1：

输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
   2
  3 4
 6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

示例 2：

输入：triangle = [[-10]]
输出：-10

提示：

• 1 <= triangle.length <= 200
• triangle[0].length == 1
• triangle[i].length == triangle[i - 1].length + 1
• -10^4 <= triangle[i][j] <= 10^4

二、解题思路

这个问题可以通过动态规划来解决。我们可以从三角形的底部开始，逐层向上计算每个节点到底部的最小路径和。对于每个节点，其最小路径和等于其值加上其下一层相邻节点的最小路径和。这样，当我们计算到三角形的顶部时，顶部的值就是整个三角形的最小路径和。

具体步骤如下：

1. 初始化一个与三角形相同大小的二维数组dp，用于存储每个节点到底部的最小路径和。
2. 从三角形的最后一行开始，将这一行的值复制到dp的对应行。
3. 从倒数第二行开始，逐行向上计算，对于每一行的每个节点，其最小路径和为该节点的值加上其下一行相邻节点的最小路径和中的较小值。
4. 当计算到三角形的顶部时，dp[0][0]就是整个三角形的最小路径和。
5. 返回dp[0][0]作为结果。

三、具体代码

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[][] dp = new int[n][n];
        
        // 初始化dp数组的最后一行
        for (int i = 0; i < n; i++) {
            dp[n - 1][i] = triangle.get(n - 1).get(i);
        }
        
        // 从倒数第二行开始向上计算
        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[i][j] = triangle.get(i).get(j) + Math.min(dp[i + 1][j], dp[i + 1][j + 1]);
            }
        }
        
        // 返回顶部节点的最小路径和
        return dp[0][0];
    }
}

四、时间复杂度和空间复杂度

1. 时间复杂度

• 初始化dp数组的最后一行需要遍历n个元素，时间复杂度为O(n)。
• 双层循环中，外层循环执行了n-1次，内层循环在最坏情况下（即倒数第二行）执行了n-1次。
• 因此，内层循环的总执行次数是1 + 2 + 3 + … + (n-1)，这是一个等差数列求和，其和为((1 + n-1) * (n-1)) / 2。
• 综合外层循环和内层循环，总的时间复杂度是O(n^2)。

2. 空间复杂度

• dp数组的大小为n x n，用于存储每一行的最小路径和。
• 因此，空间复杂度主要取决于dp数组的大小，即O(n^2)。

综上所述，代码的时间复杂度是O(n^2)，空间复杂度是O(n^2)。

五、总结知识点

1. 动态规划：这是一种通过将问题分解为更小的子问题来解决复杂问题的方法，通常用于优化问题，如最短路径、最大子数组和等。

2. 二维数组：dp是一个二维数组，用于存储每一行的最小路径和。在Java中，它被初始化为int[n][n]，其中n是三角形的行数。

3. 列表（List）的使用：List<List<Integer>> triangle 是一个包含整数列表的列表，用于存储杨辉三角的数据。在这里，它被用来存储输入的三角形。

4. 循环结构：for 循环用于重复执行一系列操作。这里有双层循环，外层循环用于控制行数，内层循环用于计算每一行的最小路径和。

5. 数学函数：Math.min() 函数用于返回两个整数中的较小值。

6. 数组的索引操作：在更新每一行元素时，代码通过索引来访问和修改二维数组中的元素。

7. 列表的元素访问：triangle.get(i).get(j) 用于获取列表中索引为 i 的子列表中索引为 j 的元素值。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。