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 is11
(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的更多相关文章
-
LeetCode 120. Triangle (三角形)
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent n ...
-
leetcode 120 Triangle ----- java
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent n ...
-
[LeetCode] 120. Triangle _Medium tag: Dynamic Programming
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent n ...
-
[leetcode 120]triangle 空间O(n)算法
1 题目 Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjac ...
-
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 ...
-
[leetcode] 120. Triangle (Medium)
原题 思路: dp,从下往上依次取得最小的,取到最上面的,就是一条最小的路径. class Solution { public: int minimumTotal(vector<vector&l ...
-
LeetCode 120. Triangle三角形最小路径和 (C++)
题目: Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjace ...
-
LeetCode 120. Triangle (三角形最小路径和)详解
题目详情 给定一个三角形,找出自顶向下的最小路径和.每一步只能移动到下一行中相邻的结点上. 例如,给定三角形: [ [2], [3,4], [6,5,7], [4,1,8,3] ] 自顶向下的最小路径 ...
-
[leetcode]120.Triangle三角矩阵从顶到底的最小路径和
Given a triangle, find the minimum path sum from top to bottom.Each step you may move to adjacent nu ...
随机推荐
-
SQLServer学习笔记系列3
一.写在前面的话 今天又是双休啦!生活依然再继续,当你停下来的时候,或许会突然显得不自在.有时候,看到一种东西,你会发现原来在这个社会上,优秀的人很多,默默 吃苦努力奋斗的人也多!星期五早上按时上班, ...
-
Stuts2的";struts.devMode";设置成true后,不起作用,仍需要重启tomcat
在项目的struts.xml加入了常量配置:<constant name="struts.devMode" value="true" />后,重启服 ...
-
poj 3349:Snowflake Snow Snowflakes(哈希查找,求和取余法+拉链法)
Snowflake Snow Snowflakes Time Limit: 4000MS Memory Limit: 65536K Total Submissions: 30529 Accep ...
-
弹出框页面中使用jquery.validate验证控件
弹出框页面中使用jquery.validate验证控件有几个问题需要解决: 1,弹出框的提交事件完成后如何关闭弹出框页面? 2,提交不成功如何返回当前页? 3,如果知道验证事件成功? 之前笔者都是JS ...
-
一个PHP常用表单验证类(基于正则)
一个基于正则表达式的PHP常用表单验证类,作者:欣然随风.这个表单判断类的功能有:验证是否为指定长度的字母/数字组合.验证是否为指定长度汉字.身 份证号码验证.是否是指定长度的数字.验证邮件地址.电话 ...
-
进入MFC讲坛的前言(四)
MFC的消息映射机制 MFC的设计者们在设计MFC时,紧紧把握一个目标,那就是尽可能使得MFC的代码要小,速度尽可能快.为了这个目标,他们使用了许多技巧,其中很多技巧体现在宏的运用上,实现MFC的消息 ...
-
写插件时遇到的一个小问题,关于animate和css3的问题
昨天写代码时,偶然想到了如果我们把css3属性放在animate中,指定时间.能否实现动画呢.举个例子吧: <script> $(".box").animate({ & ...
-
MVC分页控件的使用
1. 引用 using Webdiyer.WebControls.Mvc; 2. using Webdiyer.WebControls.Mvc; ) { )); } 3.数据来源 public cla ...
-
Sublime Text中安装插件来实现px与rem间的换算
今天在群里无意中看到了群友分享的一篇关于移动端的文章.里面其他内容我倒不大感兴趣,反而是rem让我提起了兴趣. 首先来谈一下rem,rem是CSS3中新增加的一个单位值,它和em单位一样,都是一个相对 ...
-
PHP无限极分类原理
1.递归:程序调用自身的编程技巧称为递归 2.案例: /** * @param 递归 $[name] */ function deeploop(&$i=1){ echo $i; $i++; i ...