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

相关文章

来自专栏有趣的Python

玩转算法面试:(四)LeetCode查找类问题

查找问题 两类查找问题 查找有无:元素’a’是否存在?set;集合 查找对应关系(键值对应):元素’a’出现了几次?map;字典 通常语言的标准库中都内置set...

3296
来自专栏King_3的技术专栏

leetcode-162-寻找峰值

给定一个输入数组 nums,其中 nums[i] ≠ nums[i+1],找到峰值元素并返回其索引。

543
来自专栏King_3的技术专栏

leetcode-581-Shortest Unsorted Continuous Subarray

945
来自专栏calmound

HDU 3555 Bomb(数位DP)

http://acm.hdu.edu.cn/showproblem.php?pid=3555 题意:0-n之间有多少个数包含"13"的 分析:dp[pos][h...

2605
来自专栏LeetCode

LeetCode 169. Majority Element

思路:数组中有一个数字的出现次数超过一半,也就是说这个数字的出现次数比其他的所有的数字的出现次数之和还要多。因此我们可以考虑遍历数组的时候保存两个值,一个是数组...

331
来自专栏青青天空树

小白详细讲解快速幂--杭电oj2035-A^B

输入数据包含多个测试实例,每个实例占一行,由两个正整数A和B组成(1<=A,B<=10000),如果A=0, B=0,则表示输入数据的结束,不做处理。

943
来自专栏desperate633

LeetCode 115. Distinct Subsequences题目分析代码

给出字符串S和字符串T,计算S的不同的子序列中T出现的个数。 子序列字符串是原始字符串通过删除一些(或零个)产生的一个新的字符串,并且对剩下的字符的相对位置没...

612
来自专栏小樱的经验随笔

51Nod 1090 3个数和为0(暴力)

1090 3个数和为0 基准时间限制:1 秒 空间限制:131072 KB 分值: 5         难度:1级算法题 给出一个长度为N的无序数组,数组中的元...

2616
来自专栏武培轩的专栏

Leetcode#344. Reverse String(反转字符串)

532
来自专栏HelloCode开发者学习平台

BAT面试算法进阶(1)-两个数求和

Given an array of integers, return indices of the two numbers such that they add...

804

扫码关注云+社区