当前位置：首页 > news >正文

【LeetCode 每日一题】120. 三角形最小路径和——（解法二）自底向上 - 实践

news 2025/10/22 16:35:05

【LeetCode 每日一题】120. 三角形最小路径和——（解法二）自底向上 - 实践

Problem:120. 三角形最小路径和

文章目录

整体思路
完整代码
时空复杂度
- 时间复杂度：O(N^2)
- 空间复杂度：O(N^2)

整体思路

这段代码旨在解决经典的“三角形最小路径和”难题。与上一个自顶向下的递归+记忆化版本不同，此版本采用了一种自底向上 (Bottom-up) 的、迭代式的动态规划方法。这种方法通常在空间上更易于优化，且没有递归开销。

状态定义：
- 算法使用一个二维DP数组 dp。
- dp[i][j] 在此解法中被定义为：从三角形底部出发，到达位置 (i, j) 的最小路径和。
- 这个定义与自顶向下的定义（从 (i, j) 出发到终点）有所不同，但最终求解的目标是一致的。另一种更直观的理解是，dp[i][j] 就是原问题中“从顶点出发到(i,j)的最小路径和”，但通过自底向上的方式来计算。然而，根据代码的转移方程，第一种定义更贴切。
状态转移方程：
- 为了计算从底部到达 (i, j) 的最小路径和，我们必须从下一行的 (i+1, j) 或 (i+1, j+1) 这两个位置之一移动上来。
- 因此，到达 (i, j) 的最小路径和，等于 (i, j) 本身的值，加上到达 (i+1, j) 和 (i+1, j+1) 这两个位置的最小路径和中，较小的那一个。
- 这形成了状态转移方程：
  dp[i][j] = triangle.get(i).get(j) + Math.min(dp[i+1][j], dp[i+1][j+1])
算法步骤：
- 初始化：
  - 创建一个 n x n 的 dp 数组。
  - 基础情况：算法从三角形的最底一行 (n-1) 开始。对于最底一行的任何一个节点 (n-1, i)，从底部到达它自身的最小路径和就是它本身的值。
  - 所以，通过一个循环 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++): 对于第 i 行的每一个节点 j，应用上面的状态转移方程，计算出 dp[i][j] 的值。
  - 由于我们是自底向上计算，当计算 dp[i][j] 时，它所依赖的 dp[i+1][j] 和 dp[i+1][j+1] 的值都已经被计算出来了，这保证了DP的无后效性。
- 最终结果：
  - 当循环结束，一直计算到 i=0 时，dp[0][0] 中存储的就是从底部到达顶部顶点 (0,0) 的最小路径和，这也就是整个问题的答案。

完整代码

import java.util.List;
class Solution {
/**
* 计算三角形的最小路径和（自底向上 DP）。
* @param triangle 一个表示数字三角形的列表的列表
* @return 最小路径和
*/
public int minimumTotal(List<List<Integer>> triangle) {int n = triangle.size();// dp[i][j]: 从底部出发，到达位置 (i, j) 的最小路径和。int[][] dp = new int[n][n];// 步骤 1: 初始化基础情况，即三角形的最后一行。// 从底部到达最后一行的任意节点 (n-1, i)，其最小路径和就是该节点自身的值。for (int i = 0; i < n; i++) {dp[n - 1][i] = triangle.get(n - 1).get(i);}// 步骤 2: 自底向上进行迭代// 从倒数第二行 (n-2) 开始，一直计算到第一行 (0)。for (int i = n - 2; i >= 0; i--) {// 遍历第 i 行的每一个节点 jfor (int j = 0; j <= i; j++) {// 应用状态转移方程：// 到达 (i,j) 的最小路径和 = (i,j)的值 + min(到达(i+1,j)的最小和, 到达(i+1,j+1)的最小和)dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle.get(i).get(j);}}// 步骤 3: 最终结果存储在 dp[0][0]// 它代表从底部到达顶点 (0,0) 的最小路径和。return dp[0][0];}}