[LeetCode] 120. Triangle

【原题】 Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below. For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11). 【解释】 给定一个三角形的数组,数组中的数值代表路径的长度。要求返回从第一行到最后一行的最短路径。 【思路】 这道题一看就知道是DP类问题,由于最后返回的的是一个和,如果我们从第一行开始,我们并不知道最后一行的时候最短路径会经过哪一个元素,但是可以肯定的是肯定会经过第一行的哪一个元素,所以我们从最后一行开始求,最后返回dp数组的第一个元素即可。假设dp保存的是已经求好的最短路径,当前行的第i个元素(值为n)的最短路径为dp[i]=min(dp[i],dp[i+1])+n。 代码如下:

public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
      int m=triangle.size();
        //int n=triangle[0].length;//刚开始还想申请二维数组来着
        int[] dp=new int[m+1];
        for(int i=m-1;i>=0;i--){
            List<Integer> row=triangle.get(i);
            for(int j=0;j<row.size();j++){
                dp[j]=Math.min(dp[j+1],dp[j])+row.get(j);//递推公式
            }
        }
        return dp[0];
   }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏尾尾部落

希尔排序【Shellsort】

希尔排序是基于插入排序的以下两点性质而提出改进方法的: – 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率 – 但插入排序一般来说...

733
来自专栏机器学习从入门到成神

数据库中关系代数中的关系运算

这个概念的描述的非常抽象,刚开始学习的同学完全不知所云。这里通过一个实例来说明除法运算的求解过程:

7152
来自专栏章鱼的慢慢技术路

排序算法的实现与比较

1618
来自专栏Crossin的编程教室

【编程课堂】震惊!小 bug 引发大灾难,0.1 + 0.2 的结果竟然是……

各位观众点进标题看文章的时候,我已经准备打包行李去UC报道啦~ 冷笑话结束,嗯,说正事。 请大家思考一下在 python 控制台输入 0.1 + 0.2 ==...

2759
来自专栏机器学习从入门到成神

数据库闭包和候选码求解方法

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

3941
来自专栏Java爬坑系列

【Java入门提高篇】Day22 Java容器类详解(五)HashMap源码分析(上)

准备了很长时间,终于理清了思路,鼓起勇气,开始介绍本篇的主角——HashMap。说实话,这家伙能说的内容太多了,要是像前面ArrayList那样翻译一下源码,稍...

2165
来自专栏老九学堂

【干货】小白如何熟练掌握C语言随机数!

随机数的使用,是不少小伙伴在学C语言过程中都会遇到的一个坎,今天老九为大家讲解如何在C语言中使用随机数。 通常情况下,使用最多的方法的就是使用rand函数随机生...

4057
来自专栏程序员的SOD蜜

Why to do,What to do,Where to do 与 Lambda表达式!

最近我做一个“四象限”图表控件,其中有一个比较复杂的“坐标变换”问题,即是如何让一组数据放到有限的一个区间内,例如有一组数据 List[4,5,6,7,8],要...

2179
来自专栏云霄雨霁

关系代数

1410
来自专栏机器学习和数学

[Tensorflow] TensorFlow之Hello World!(2)

TensorFlow入门的第一篇和大家聊了?graph图,op操作,node节点。对TensorFlow有了一个简单的认识,今天主要和大家分享的是TensorF...

3577

扫码关注云+社区