贴个动归解释，这个是我见过解释的最清楚的，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。

代码

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 。

最后

以上就是欢喜百褶裙为你收集整理的【每日一道算法题】Leetcode之triangle 三角形求最小路径和问题 Java 动态规划题目描述例子代码解释的全部内容，希望文章能够帮你解决【每日一道算法题】Leetcode之triangle 三角形求最小路径和问题 Java 动态规划题目描述例子代码解释所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。