【每日一道算法题】Leetcode之triangle 三角形求最小路径和问题 Java 动态规划题目描述例子代码解释

107 阅读 0 评论 71 点赞

我是靠谱客的博主欢喜百褶裙，这篇文章主要介绍【每日一道算法题】Leetcode之triangle 三角形求最小路径和问题 Java 动态规划题目描述例子代码解释，现在分享给大家，希望可以做个参考。

贴个动归解释，这个是我见过解释的最清楚的，mark一下动态规划答疑篇

题目描述

给出一个三角形，计算从三角形顶部到底部的最小路径和，每一步都可以移动到下面一行相邻的数字，

例子

例如，给出的三角形如下：[↵ [2],↵ [3,4],↵ [6,5,7],↵ [4,1,8,3]↵]
在这里插入图片描述
最小的从顶部到底部的路径和是2 + 3 + 5 + 1 = 11。
再例如：给出的三角形如下：[↵ [-1],↵ [2,3],↵ [1,-1,-3]]

最小的从顶部到底部的路径和是-1 + 3 + -3 = -1。

代码

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.util.*;
public class Solution {
    public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
	        ArrayList<Integer> listPre=triangle.get(0);//上一层的值 
	        ArrayList<Integer> list=null;//这一层的值
	        ArrayList<Integer> listMin=triangle.get(0);//总和
	        for(int i=1;i<triangle.size();i++){
	            listMin=new ArrayList<>();//每一层的总和
	            list=triangle.get(i);
	            for(int j=0;j<list.size();j++){
	            	int min;
	            	if (j-1<0) {//j超出listPre的范围
						min=listPre.get(j);
					}else if (j>=listPre.size()) {
						min=listPre.get(j-1);
					}else{
						min=Math.min(listPre.get(j),listPre.get(j-1));
					}
	                listMin.add(list.get(j)+min);
	            }
	            listPre=listMin;
	        }
	        //找出最大的
	        Collections.sort(listMin);
	        return listMin.get(0);
	    }
}

解释

首先，不能用贪心。因为如果最后一层有一个很小很小的值，但是前面没有选择到，就得不到最终的答案。
接着分析，可不可以分解为最优子问题。那么，进行拆分，如下图所示。
在这里插入图片描述
0-2层的结果和0-3层的结果有什么关系呢？
如果我们得到0-2层的最优结果，怎么得到最终的结果呢？

这里假设到达第2层每个元素最小路径和是 6 5 7 。