LeetCode - 120. Triangle

时间:2021-08-20 12:14:28

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). Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle. 思路:简单DP,把到每一个点的最优路径算出来,利用上面算好的结果。最后选最后一层的最优解。

1,动态规划。到第i层的第k个顶点的最小路径长度表示为f(i,k),则f(i, k) = min{f(i-1,k),  f(i-1,k-1)} + d(i, k); 其中d(i, k)表示原来三角形数组里的第i行第k列的元素。则可以求得从第一行到最终到第length-1行第k个元素的最小路径长度,最后再比较第length-1行中所有元素的路径长度大小,求得最小值。

2,本题主要关心的是空间复杂度不要超过n。

3,注意边界条件——每一行中的第一和最后一个元素在上一行中只有一个邻居。而其他中间的元素在上一行中都有两个相邻元素。

代码:

import java.util.*;
public class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
if (triangle == null || triangle.get(0) == null)
return 0; int iLen = triangle.size(); for (int i=1; i<iLen; i++) {
int jLen = triangle.get(i).size();
for (int j=0; j<jLen; j++) {
if (j == 0) {
triangle.get(i).set(0, triangle.get(i).get(0) + triangle.get(i-1).get(0));
}
else if (j == jLen - 1) {
triangle.get(i).set(j, triangle.get(i).get(j) + triangle.get(i-1).get(j-1));
}
else {
triangle.get(i).set(j, triangle.get(i).get(j) + Math.min(triangle.get(i-1).get(j-1), triangle.get(i-1).get(j)));
}
}
} return Collections.min(triangle.get(iLen-1));
}
}

LeetCode - 120. Triangle的更多相关文章

  1. LeetCode 120&period; Triangle (三角形)

    Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent n ...

  2. leetcode 120 Triangle ----- java

    Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent n ...

  3. &lbrack;LeetCode&rsqb; 120&period; Triangle &lowbar;Medium tag&colon; Dynamic Programming

    Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent n ...

  4. &lbrack;leetcode 120&rsqb;triangle 空间O&lpar;n&rpar;算法

    1 题目 Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjac ...

  5. Java for LeetCode 120 Triangle

    Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent n ...

  6. &lbrack;leetcode&rsqb; 120&period; Triangle (Medium)

    原题 思路: dp,从下往上依次取得最小的,取到最上面的,就是一条最小的路径. class Solution { public: int minimumTotal(vector<vector&l ...

  7. LeetCode 120&period; Triangle三角形最小路径和 &lpar;C&plus;&plus;&rpar;

    题目: Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjace ...

  8. LeetCode 120&period; Triangle &lpar;三角形最小路径和)详解

    题目详情 给定一个三角形,找出自顶向下的最小路径和.每一步只能移动到下一行中相邻的结点上. 例如,给定三角形: [ [2], [3,4], [6,5,7], [4,1,8,3] ] 自顶向下的最小路径 ...

  9. &lbrack;leetcode&rsqb;120&period;Triangle三角矩阵从顶到底的最小路径和

    Given a triangle, find the minimum path sum from top to bottom.Each step you may move to adjacent nu ...

随机推荐

  1. SQLServer学习笔记系列3

    一.写在前面的话 今天又是双休啦!生活依然再继续,当你停下来的时候,或许会突然显得不自在.有时候,看到一种东西,你会发现原来在这个社会上,优秀的人很多,默默 吃苦努力奋斗的人也多!星期五早上按时上班, ...

  2. Stuts2的&quot&semi;struts&period;devMode&quot&semi;设置成true后,不起作用,仍需要重启tomcat

    在项目的struts.xml加入了常量配置:<constant name="struts.devMode" value="true" />后,重启服 ...

  3. poj 3349&colon;Snowflake Snow Snowflakes(哈希查找,求和取余法&plus;拉链法)

    Snowflake Snow Snowflakes Time Limit: 4000MS   Memory Limit: 65536K Total Submissions: 30529   Accep ...

  4. 弹出框页面中使用jquery&period;validate验证控件

    弹出框页面中使用jquery.validate验证控件有几个问题需要解决: 1,弹出框的提交事件完成后如何关闭弹出框页面? 2,提交不成功如何返回当前页? 3,如果知道验证事件成功? 之前笔者都是JS ...

  5. 一个PHP常用表单验证类&lpar;基于正则&rpar;

    一个基于正则表达式的PHP常用表单验证类,作者:欣然随风.这个表单判断类的功能有:验证是否为指定长度的字母/数字组合.验证是否为指定长度汉字.身 份证号码验证.是否是指定长度的数字.验证邮件地址.电话 ...

  6. 进入MFC讲坛的前言&lpar;四&rpar;

    MFC的消息映射机制 MFC的设计者们在设计MFC时,紧紧把握一个目标,那就是尽可能使得MFC的代码要小,速度尽可能快.为了这个目标,他们使用了许多技巧,其中很多技巧体现在宏的运用上,实现MFC的消息 ...

  7. 写插件时遇到的一个小问题,关于animate和css3的问题

    昨天写代码时,偶然想到了如果我们把css3属性放在animate中,指定时间.能否实现动画呢.举个例子吧: <script> $(".box").animate({ & ...

  8. MVC分页控件的使用

    1. 引用 using Webdiyer.WebControls.Mvc; 2. using Webdiyer.WebControls.Mvc; ) { )); } 3.数据来源 public cla ...

  9. Sublime Text中安装插件来实现px与rem间的换算

    今天在群里无意中看到了群友分享的一篇关于移动端的文章.里面其他内容我倒不大感兴趣,反而是rem让我提起了兴趣. 首先来谈一下rem,rem是CSS3中新增加的一个单位值,它和em单位一样,都是一个相对 ...

  10. PHP无限极分类原理

    1.递归:程序调用自身的编程技巧称为递归 2.案例: /** * @param 递归 $[name] */ function deeploop(&$i=1){ echo $i; $i++; i ...