当前位置:网站首页>LeetCode 120. 三角形最小路径和 每日一题
LeetCode 120. 三角形最小路径和 每日一题
2022-07-07 15:32:00 【@小红花】
问题描述
给定一个三角形 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 <= triangle.length <= 200
triangle[0].length == 1
triangle[i].length == triangle[i - 1].length + 1
-104 <= triangle[i][j] <= 104来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/triangle
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
Java
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int row = triangle.size();
int[] dp = new int[row];
dp[0] = triangle.get(0).get(0);
for(int i = 1;i < row;i++){
dp[i] = dp[i - 1] + triangle.get(i).get(i);
for(int j = i - 1;j > 0;j--){
dp[j] = Math.min(dp[j],dp[j - 1]) + triangle.get(i).get(j);
}
dp[0] += triangle.get(i).get(0);
}
int ans = Integer.MAX_VALUE;
for(int n : dp){
ans = Math.min(ans,n);
}
return ans;
}
}
边栏推荐
- Pycharm terminal enables virtual environment
- LocalStorage和SessionStorage
- [C language] question set of X
- LeetCode 1774. 最接近目标价格的甜点成本 每日一题
- How can laravel get the public path
- 如何快速检查钢网开口面积比是否符合 IPC7525
- DAPP defi NFT LP single and dual currency liquidity mining system development details and source code
- 1亿单身男女“在线相亲”,撑起130亿IPO
- Ray and OBB intersection detection
- Temperature sensor chip used in temperature detector
猜你喜欢
随机推荐
SqlServer2014+: 创建表的同时创建索引
Horizontal and vertical centering method and compatibility
Personal notes of graphics (2)
运算符
记录Servlet学习时的一次乱码
The differences between exit, exit (0), exit (1), exit ('0 '), exit ('1'), die and return in PHP
Lowcode: four ways to help transportation companies enhance supply chain management
Cesium(3):ThirdParty/zip. js
Imitate the choice of enterprise wechat conference room
23. 合并K个升序链表-c语言
水平垂直居中 方法 和兼容
【DesignMode】模板方法模式(Template method pattern)
Common training data set formats for target tracking
Sqlserver2014+: create indexes while creating tables
JS 模块化
01tire+链式前向星+dfs+贪心练习题.1
typescript ts基础知识之tsconfig.json配置选项
二叉搜索树(特性篇)
Personal notes of graphics (3)
无法将“pip”项识别为 cmdlet、函数、脚本文件或可运行程序的名称