DeepSeek LeetCode 120. 三角形最小路径和 Java实现

LeetCode 120. 三角形最小路径和 Java 实现

题目理解

给定一个三角形 triangle，返回从顶部到底部的最小路径和。每一步只能移动到下一行中相邻的节点。

例如：

2
3 4
6 5 7
4 1 8 3

最小路径和为 2 + 3 + 5 + 1 = 11。

解法一：二维 DP（自顶向下）

定义 dp[i][j] 为从顶部走到位置 (i, j) 的最小路径和。

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 j = 1; j < i; j++) {
dp[i][j] = Math.min(dp[i – 1][j – 1], dp[i – 1][j])
+ triangle.get(i).get(j);
}

// 最右列只能从上一行最右列过来
dp[i][i] = dp[i – 1][i – 1] + triangle.get(i).get(i);
}

int ans = dp[n – 1][0];
for (int j = 1; j < n; j++) {
ans = Math.min(ans, dp[n – 1][j]);
}
return ans;
}
}

· 时间复杂度：O(n²)
· 空间复杂度：O(n²)

解法二：一维 DP（自底向上，推荐）

从倒数第二行开始向上递推。
dp[j] 表示从当前行第 j 个位置到底部的最小路径和。

初始化 dp 为最后一行的值，然后向上更新：

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

// 初始化最后一行的值
for (int j = 0; j < n; j++) {
dp[j] = triangle.get(n – 1).get(j);
}

// 从倒数第二行开始向上递推
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];
}
}

· 时间复杂度：O(n²)
· 空间复杂度：O(n)

解法三：原地修改（额外空间 O(1)）

如果允许修改原三角形，可以直接在 triangle 上从下往上累加，最终 triangle.get(0).get(0) 就是答案。

class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
for (int i = triangle.size() – 2; i >= 0; i—) {
for (int j = 0; j <= i; j++) {
int min = Math.min(triangle.get(i + 1).get(j),
triangle.get(i + 1).get(j + 1));
triangle.get(i).set(j, triangle.get(i).get(j) + min);
}
}
return triangle.get(0).get(0);
}
}

· 时间复杂度：O(n²)
· 空间复杂度：O(1)（不计输入本身）

总结

解法 时间复杂度 空间复杂度 特点
二维 DP O(n²) O(n²) 思路直观，易于理解
一维 DP（自底向上） O(n²) O(n) 推荐，不修改输入
原地修改 O(n²) O(1) 空间最优，但会修改输入

面试建议：优先写一维 DP 自底向上的解法，代码简洁、空间优化好，且不破坏输入数据。