Java算法题-解析三角形最小路径和问题

题目

给定一个三角形 triangle，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的节点上。

例如，给定以下三角形：

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

自顶向下的最小路径和为 11（2 + 3 + 5 + 1 = 11）。

注意： 你可以只使用 O(n) 的额外空间，其中 n 是三角形的总行数。

引言

这是一个经典的动态规划问题，需要找出从顶部到底部的最小路径和。我们可以使用动态规划来解决它，自底向上地计算最小路径和。

算法思路

我们可以使用一个二维数组 dp 来存储每个节点的最小路径和。dp[i][j] 表示从三角形的第 i 行第 j 列节点出发的最小路径和。

动态规划的关键是找出状态转移方程。在这个问题中，我们可以观察到以下性质：

• 对于三角形的最底层（最后一行），最小路径和等于自身的值，即 dp[n-1][j] = triangle[n-1][j]，其中 n 是三角形的行数。
• 对于三角形的其他行，从下一行到当前行的最小路径和可以由下一行的相邻节点的最小路径和决定。具体地，dp[i][j] = triangle[i][j] + min(dp[i+1][j], dp[i+1][j+1])，其中 min 表示取最小值。

最终，dp[0][0] 就是从顶部到底部的最小路径和。

代码实现

以下是使用 Java 实现的解决方案：

import java.util.List;

public class TriangleMinPathSum {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[][] dp = new int[n][n];

        // 初始化最底层的最小路径和
        for (int j = 0; j < n; j++) {
            dp[n - 1][j] = triangle.get(n - 1).get(j);
        }

        // 自底向上计算最小路径和
        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];
    }
}

算法分析

• 时间复杂度：遍历每个节点一次，所以时间复杂度是O(n^2)，其中 n 是三角形的总行数。
• 空间复杂度：使用了一个二维数组 dp 来存储最小路径和，所以空间复杂度是O(n^2)。

示例和测试

假设给定一个示例三角形 triangle，如下所示：

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

我们可以使用以下代码进行测试：

public class Main {
    public static void main(String[] args) {
        TriangleMinPathSum solution = new TriangleMinPathSum();
        List<List<Integer>> triangle = new ArrayList<>();
        triangle.add(Arrays.asList(2));
        triangle.add(Arrays.asList(3, 4));
        triangle.add(Arrays.asList(6, 5, 7));
        triangle.add(Arrays.asList(4, 1, 8, 3));

        int result = solution.minimumTotal(triangle);
        System.out.println("Minimum total path sum: " + result);
    }
}

总结

求解三角形最小路径和是一个典型的动态规划问题，需要找出从顶部到底部的最小路径和。我们使用动态规划自底向上地计算最小路径和，利用一个二维数组 dp 来存储每个节点的最小路径和。这个问题的时间复杂度是O(n^2)，空间复杂度是O(n^2)。动态规划是解决类似问题的常用方法，有助于理解状态转移和最优子结构的概念。