最新消息:XAMPP默认安装之后是很不安全的,我们只需要点击左方菜单的 "安全"选项,按照向导操作即可完成安全设置。

数组篇15_三角形最小路径和求解

XAMPP相关 admin 508浏览 0评论

来源:LeetCode

难度:中等

描述:

给定一个三角形 triangle ,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说,如果正位于当前行的下标 i ,那么下一步可以移动到下一行的下标 i 或 i + 1 。

示例1:

drf0041

实例2:

drf00041

分析:题意很好理解,就是让咱们在三角形中找出一条数值最小的路径,并返回这个和,这个和之前的杨辉三角有点类似,咱们可以自顶向下暴力遍历,也可以自下向上选取,以下是具体解法

解题

方法一:自顶向下暴力遍历

思路:采用递归的方式,从顶部往下遍历,在下一行的第 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_三角形最小路径和求解

您必须 登录 才能发表评论!