Triangle leetcode java
2024-08-26 02:04:47
题目:
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).
Note:
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[i][j] = dp[i+1][j] + dp[i+1][j+1] ,当前这个点的最小值,由他下面那一行临近的2个点的最小值与当前点的值相加得到。
由于是三角形,且历史数据只在计算最小值时应用一次,所以无需建立二维数组,每次更新1维数组值,最后那个值里存的就是最终结果。
代码如下:
1 public int minimumTotal(List<List<Integer>> triangle) {
2 if(triangle.size()==1)
3 return triangle.get(0).get(0);
4
5 int[] dp = new int[triangle.size()];
6
7 //initial by last row
8 for (int i = 0; i < triangle.get(triangle.size() - 1).size(); i++) {
9 dp[i] = triangle.get(triangle.size() - 1).get(i);
}
// iterate from last second row
for (int i = triangle.size() - 2; i >= 0; i--) {
for (int j = 0; j < triangle.get(i).size(); j++) {
dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j);
}
}
return dp[0];
}
Reference: http://www.programcreek.com/2013/01/leetcode-triangle-java/
最新文章
- nios II--实验3——led 100M硬件部分
- Java文件内容的复制
- Swift-05-SizeOf&;&;SizeOfValue
- JavaScript内的类型转换
- D3js
- usaco /the second wave
- iis虚拟目录引发的路径问题
- PreparedStatemnet预编译操作数据库的增删改
- Linux手动搭建LAMP环境
- 《程序设计实践》【PDF】下载
- MySQL入门笔记(二)
- Linux kernel的中断子系统之(二):IRQ Domain介绍
- BZOJ_1212_[HNOI2004]L语言_哈希
- Redis+Restful 构造序列号和压力测试【后续】
- mysql学习笔记--go使用mysql
- 干货---stm32f103之DMA双缓冲__也算我为网络贡献的微薄之力
- 【干货】Jquery.Datables与Bootstrap3的组合使用
- day052-53 django框架
- python之字典(dict)
- ASP.NET MVC:WebPageRenderingBase.cs
热门文章
- 如何使用windows云服务器搭建IIs、windows服务
- x270
- web压力测试工具(小而精)
- Redis使用小结
- Project 03- STM32F4xx PID controller
- Echarts学习记录——如何去掉网格线及网格区域颜色
- 【Go命令教程】7. go run
- 《Linux设备驱动开发详解(第3版)》(即《Linux设备驱动开发详解:基于最新的Linux 4.0内核》)--宋宝华
- Entity Framework 6 (7) vs NHibernate 4: DDD perspective(纯净DDD很难很难...)
- Delphi2010 RTTI + Attribute 简单实现ORM实例