三角形最小路径和
难度:
标签:
题目描述
给定一个三角形 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 <= 200triangle[0].length == 1triangle[i].length == triangle[i - 1].length + 1-104 <= triangle[i][j] <= 104
进阶：
- 你可以只使用
O(n)的额外空间（n为三角形的总行数）来解决这个问题吗？
代码结果
运行时间: 20 ms, 内存: 18.1 MB
/*
* 思路：
* 1. 使用Java Stream API从底部向顶部迭代计算最小路径和。
* 2. 通过map和reduce方法实现动态规划的状态更新。
*/
import java.util.List;
import java.util.stream.Collectors;
public class SolutionStream {
public int minimumTotal(List<List<Integer>> triangle) {
// 从最后一行开始，使用stream逐行向上计算
return triangle.stream()
.reduce((prev, curr) ->
curr.stream()
.map(i -> i + Math.min(prev.get(curr.indexOf(i)), prev.get(curr.indexOf(i) + 1)))
.collect(Collectors.toList())
)
.get()
.get(0);
}
}
解释
方法:
该题解使用动态规划的思路来解决问题。首先初始化一个二维 DP 数组，用于存储从三角形顶部到达每个位置的最小路径和。然后从第二行开始，逐行填充 DP 数组。对于每个位置，根据它的索引情况，选择上一行相邻位置中的较小值，加上当前位置的值，更新 DP 数组。最后，返回 DP 数组最后一行的最小值，即为从顶部到底部的最小路径和。
时间复杂度:
O(n^2)
空间复杂度:
O(n^2)，可优化为 O(n)
代码细节讲解
🦆
动态规划方法中，初始化每个 dp[i][j] 为 0 是否会影响最终的路径和计算？
▷🦆
在题解中，对于边界元素的处理（如最左边和最右边的元素），它们的状态转移方程与中间元素的处理有何不同？能否详细解释这种区别？
▷🦆
在最终返回最小路径和时，你选择返回 dp[n-1] 的最小值，这里为什么不直接返回 dp[n-1][0] 或 dp[n-1][n-1]？
▷