来源：LeetCode
难度：中等
描述：
给定一个三角形 triangle ，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
示例1：
实例2：
分析：题意很好理解，就是让咱们在三角形中找出一条数值最小的路径，并返回这个和，这个和之前的杨辉三角有点类似，咱们可以自顶向下暴力遍历，也可以自下向上选取，以下是具体解法
解题
方法一：自顶向下暴力遍历
思路：采用递归的方式，从顶部往下遍历，在下一行的第 i 个位置和第 i + 1 个位置中选取较小的一个和 本位置元素相加
代码：
1public int minimumTotal(List<List<Integer>> triangle) {
2 //从顶部开始往下走
3 return dfs(triangle, 0, 0);
4}
5
6private int dfs(List<List<Integer>> triangle, int i, int j) {
7 if (i == triangle.size()) {
8 return 0;
9 }
10 //在下一行中第 j 个位置 和 第 j + 1 个位置中选取最小的那个和本位置相加
11 return Math.min(dfs(triangle, i + 1, j), dfs(triangle, i + 1, j + 1)) + triangle.get(i).get(j);
12}方法二：动态规划
思路：利用一个二维辅助数组dp，自底向上记录每行每个元素的最小路径值直到最顶部位置，直接返回dp[0][0]即可
代码：
1public int minimumTotal(List<List<Integer>> triangle) {
2 int n = triangle.size();
3 // dp[i][j] 表示从点 (i, j) 到底边的最小路径和。
4 // 这里申请的长度为n+1 所以不用对最后一行做初始化
5 int[][] dp = new int[n + 1][n + 1];
6 // 从三角形的最后一行开始递推。
7 for (int i = n - 1; i >= 0; i--) {
8 for (int j = 0; j <= i; j++) {
9 //下一行的最小的和本位置的值进行相加就是本位置最小的路径
10 dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle.get(i).get(j);
11 }
12 }
13 return dp[0][0];
14}
时间复杂度：O(n2)
空间复杂度：O(n2)
方法三：动态规划优化版
思路：思路和方法二一致，此处采用一维数组来保存中间值，因为咱们在从往上遍历的过程中只用到了下一行的元素，所以咱们只需要保存下一行的元素，不断更新即可
代码：
1public int minimumTotal(List<List<Integer>> triangle) {
2 int n = triangle.size();
3 int[] dp = new int[n + 1];
4 for (int i = n - 1; i >= 0; i--) {
5 for (int j = 0; j <= i; j++) {
6 dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j);
7 }
8 }
9 return dp[0];
10}
时间复杂度：O(n2)
空间复杂度：O(n)
以上仅是个人思路解法，觉得还不错欢迎点赞关注分享
转载请注明：XAMPP中文组官网 » 数组篇15_三角形最小路径和求解