当前位置:网站首页>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;
}
}
边栏推荐
- Set the route and optimize the URL in thinkphp3.2.3
- Horizontal and vertical centering method and compatibility
- 深度监听 数组深度监听 watch
- 字节跳动Android面试,知识点总结+面试题解析
- 【C 语言】 题集 of Ⅹ
- node:504报错
- Ray and OBB intersection detection
- Three. JS series (1): API structure diagram-1
- 最新Android高级面试题汇总,Android面试题及答案
- [C language] question set of X
猜你喜欢
3000 words speak through HTTP cache
无法将“pip”项识别为 cmdlet、函数、脚本文件或可运行程序的名称
Record the migration process of a project
1亿单身男女“在线相亲”,撑起130亿IPO
Advanced C language -- function pointer
As an Android Developer programmer, Android advanced interview
Opencv personal notes
【C 语言】 题集 of Ⅹ
字节跳动Android金三银四解析,android面试题app
Introduction and use of gateway
随机推荐
最新2022年Android大厂面试经验,安卓View+Handler+Binder
运算符
数据中台落地实施之法
LeetCode 1626. 无矛盾的最佳球队 每日一题
Temperature sensor chip used in temperature detector
Horizontal and vertical centering method and compatibility
time标准库
Three. JS series (3): porting shaders in shadertoy
Pisa-Proxy SQL 解析之 Lex & Yacc
打造All-in-One应用开发平台,轻流树立无代码行业标杆
Build an all in one application development platform, light flow, and establish a code free industry benchmark
Personal notes of graphics (4)
字节跳动高工面试,轻松入门flutter
null == undefined
【DesignMode】享元模式(Flyweight Pattern)
[designmode] flyweight pattern
Laravel5.1 Routing - routing packets
Direct dry goods, 100% praise
[vulnhub range] thales:1
LeetCode 1774. 最接近目标价格的甜点成本 每日一题