当前位置:网站首页>LeetCode 120. Triangle minimum path and daily question
LeetCode 120. Triangle minimum path and daily question
2022-07-07 16:58:00 【@Little safflower】
Problem description
Given a triangle triangle , Find the smallest sum from the top down .
Each step can only move to adjacent nodes in the next row . Adjacent nodes What I mean here is Subscript And The upper node subscript Equal to or equal to The upper node subscript + 1 Two nodes of . in other words , If it is in the subscript of the current line i , So the next step is to move to the subscript of the next line i or i + 1 .
Example 1:
Input :triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output :11
explain : As shown in the diagram below :
2
3 4
6 5 7
4 1 8 3
The minimum path sum from the top down is zero 11( namely ,2 + 3 + 5 + 1 = 11).
Example 2:Input :triangle = [[-10]]
Output :-10
Tips :
1 <= triangle.length <= 200
triangle[0].length == 1
triangle[i].length == triangle[i - 1].length + 1
-104 <= triangle[i][j] <= 104source : Power button (LeetCode)
link :https://leetcode.cn/problems/triangle
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
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;
}
}
边栏推荐
- time标准库
- Pycharm terminal enables virtual environment
- typescript ts 基础知识之类型声明
- The latest interview experience of Android manufacturers in 2022, Android view+handler+binder
- 水平垂直居中 方法 和兼容
- Imitate the choice of enterprise wechat conference room
- 网关Gateway的介绍与使用
- 第九届 蓝桥杯 决赛 交换次数
- Ray and OBB intersection detection
- Three. JS series (1): API structure diagram-1
猜你喜欢
随机推荐
ATM system
Interface oriented programming
Master this set of refined Android advanced interview questions analysis, oppoandroid interview questions
node:504报错
AutoLISP series (1): function function 1
Cesium(3):ThirdParty/zip. js
最新阿里P7技术体系,妈妈再也不用担心我找工作了
23. 合并K个升序链表-c语言
预售17.9万,恒驰5能不能火?产品力在线,就看怎么卖
The latest interview experience of Android manufacturers in 2022, Android view+handler+binder
ByteDance Android gold, silver and four analysis, Android interview question app
LocalStorage和SessionStorage
URL和URI的关系
DNS 系列(一):为什么更新了 DNS 记录不生效?
模块六
如何快速检查钢网开口面积比是否符合 IPC7525
QT中自定义控件的创建到封装到工具栏过程(二):自定义控件封装到工具栏
Opencv configuration 2019vs
skimage学习(1)
LeetCode 213. 打家劫舍 II 每日一题