目录
1.题目
- 1.题目
- 2.思路
- 3.代码实现(Java)
给定一个三角形 triangle ,找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点在这里指的是下标与上一层结点下标相同或者等于上一层结点下标 + 1 的两个结点。也就是说,如果正位于当前行的下标 i ,那么下一步可以移动到下一行的下标 i 或 i + 1。
示例 1:
输入:triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出:11
解释:如下面简图所示:
2
3 4
6 5 7
4 1 8 3
自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。
示例 2:
输入:triangle = [[-10]]
输出:-10
提示: 1 11 10 13 0 11 10 13 0 4 1 8 3 4 1 8 3 4 1 8 3 => 14 11 18 16 => 11 即为自顶向下的最小路径和
③ 在求解过程中注意要考虑边界问题,并且由于该方法使用了 n * n 的二维数组 matrix,故其空间复杂度为 O(n2)。在空间复杂度上,本题还可进一步优化,具体细节可参考本题官方题解。
相关题目: LeetCode_动态规划_中等_64.最小路径和
3.代码实现(Java)//思路1————动态规划
class Solution {
public int minimumTotal(List triangle) {
int res = Integer.MAX_VALUE;
int n = triangle.size();
if (n == 1) {
return triangle.get(0).get(0);
}
//将三角形 triangle 中的结点存储到 matrix 中(形状变为等腰直角三角形,只占 matrix 左下部分空间)
int[][] matrix = new int[n][n];
for (int i = 0; i
关注
打赏
最近更新
- 深拷贝和浅拷贝的区别(重点)
- 【Vue】走进Vue框架世界
- 【云服务器】项目部署—搭建网站—vue电商后台管理系统
- 【React介绍】 一文带你深入React
- 【React】React组件实例的三大属性之state,props,refs(你学废了吗)
- 【脚手架VueCLI】从零开始,创建一个VUE项目
- 【React】深入理解React组件生命周期----图文详解(含代码)
- 【React】DOM的Diffing算法是什么?以及DOM中key的作用----经典面试题
- 【React】1_使用React脚手架创建项目步骤--------详解(含项目结构说明)
- 【React】2_如何使用react脚手架写一个简单的页面?