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
-104 <= triangle[i][j] <= $10^4$

 解

这个问题可以使用动态规划来解决，具体步骤如下：

1. 创建一个和三角形triangle相同大小的二维数组dp，用于存储每个位置到底部的最小路径和。
2. 初始化dp的最后一行为triangle的最后一行。
3. 从倒数第二行开始，逐层计算dp数组的值。对于每个位置dp[i][j]，它的值可以通过下一层相邻的两个位置dp[i+1][j]和dp[i+1][j+1]的最小值与当前位置triangle[i][j]相加来得到，即dp[i][j] = triangle[i][j] + min(dp[i+1][j], dp[i+1][j+1])。
4. 最终，dp[0][0]就是自顶向下的最小路径和。

以下是Java代码示例：

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[][] dp = new int[n][n];
        
        // 初始化最后一行
        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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

这段代码遍历三角形的每一行，从底部开始计算每个位置的最小路径和，最后返回dp[0][0]即可。

 解2

上述解法已经是一个相对高效的解法，时间复杂度为O(n^2)，其中n是三角形的行数。如果要进一步优化，可以考虑空间复杂度的优化，因为上述解法使用了一个二维数组来存储最小路径和。

空间复杂度优化方法：

1. 不使用二维数组，而是使用一个一维数组dp来存储每一行的最小路径和。
2. 从底部往上逐层计算，每次计算时只需要使用当前行和下一行的dp值，因此可以使用滚动数组的方式，不断更新dp数组。

以下是经过空间复杂度优化的Java代码示例：

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[] dp = new int[n];
        
        // 初始化dp数组为最后一行的值
        for (int i = 0; i < n; i++) {
            dp[i] = triangle.get(n - 1).get(i);
        }
        
        // 从倒数第二行开始逐层计算
        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[j] = triangle.get(i).get(j) + Math.min(dp[j], dp[j+1]);
            }
        }
        
        return dp[0];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

这种优化后的代码在空间复杂度上更加高效，但时间复杂度仍然为O(n^2)，因为仍需遍历整个三角形。

 解3

除了动态规划的方法外，还可以使用递归加记忆化搜索的方式来解决这个问题。这种方法也被称为自顶向下的动态规划。具体思路如下：

1. 使用递归函数dfs(row, col)，表示从三角形的第row行、第col列出发，到达底部的最小路径和。
2. 递归的终止条件是row达到三角形的底部，返回三角形底部的值。
3. 在递归函数中，首先检查当前位置(row, col)是否已经计算过，如果计算过则直接返回已知的值，避免重复计算。
4. 否则，递归调用dfs(row + 1, col)和dfs(row + 1, col + 1)，然后将当前位置的值与这两个递归结果中的较小值相加，即triangle.get(row).get(col) + Math.min(dfs(row + 1, col), dfs(row + 1, col + 1))。
5. 最终返回dfs(0, 0)即为结果。

以下是Java代码示例：

class Solution {
    private List<List<Integer>> triangle;
    private Integer[][] memo;

    public int minimumTotal(List<List<Integer>> triangle) {
        this.triangle = triangle;
        this.memo = new Integer[triangle.size()][triangle.size()];
        return dfs(0, 0);
    }

    private int dfs(int row, int col) {
        if (row == triangle.size() - 1) {
            return triangle.get(row).get(col);
        }
        if (memo[row][col] != null) {
            return memo[row][col];
        }
        int left = dfs(row + 1, col);
        int right = dfs(row + 1, col + 1);
        memo[row][col] = triangle.get(row).get(col) + Math.min(left, right);
        return memo[row][col];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

这种解法的时间复杂度同样为O(n^2)，但相比于普通的递归，使用了记忆化搜索，避免了重复计算，因此效率更高。