[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 条评论
登录 后参与评论

相关文章

来自专栏深度学习计算机视觉

里式替换原则(LSP)

讲继承 所有引用父类的地方都必须可以透明的使用其子类对象 几个原则: 1、子类必须完全实现父类的方法 2、子类可以有自己的个性 3、覆盖或实现父类的方...

34112
来自专栏向治洪

Kotlin之基本语法

在今年Google IO大会上Google已经明确kotlin作为为Android第一官方语言的地位。我相信Google的决意,就像当初毫不犹豫的抛弃eclip...

2267
来自专栏海天一树

小朋友学C语言(26):冒泡排序

(一)基本原理(由小到大): 将相邻两个数比较,将大的调到后头。如果有n个数,则要进行n-1趟比较。 在第1趟中要进行n-1次两两比较,在第j趟比较中要进行n-...

3278
来自专栏用户2442861的专栏

Java基础之String中equals,声明方式,等大总结

    转载请注明出处:http://blog.csdn.net/dmk877/article/details/49420141 

522
来自专栏求索之路

Effective Java笔记(不含反序列化、并发、注解和枚举)

最近把Effective Java复习了一遍,其中有比较多的java最佳实践可以在平时编程中用到。反序列化、并发、注解和枚举这四章没看,并发这本书里讲的比较简...

33511
来自专栏Script Boy (CN-SIMO)

Qt Quick编程(1)——QML的核心部分ECMAScript

说道QML,不得不先说一下ECMAScript: ECMAScript语言的标准是由Netscape、Sun、微软、Borland等公司基于JavaScript...

2400
来自专栏小白鼠

Java8特性接口的改变LambaStream时间API

函数式接口,该接口中只能由一个抽象方法,可以使用@FunctionalInterface注解修饰某个接口有且仅有一个抽象方法。

642
来自专栏互联网杂技

JS编程小常识很有用

2.JS中的真真假假 空,null,undefined,false,0,””,'',NaN都为假,其他都为真 3.函数,类,对象,构造器有什么区别? 答:...

3196
来自专栏向治洪

Kotlin之基本语法

在今年Google IO大会上Google已经明确kotlin作为为Android第一官方语言的地位。我相信Google的决意,就像当初毫不犹豫的抛弃eclip...

2018
来自专栏PHP技术

javascript函数

函数声明提升 执行代码前会先读取函数声明,可以把函数声明放在调用他的语句后面。 sayHi(); function sayHi(){ alert("Hi!");...

3039

扫码关注云+社区