当前位置:网站首页>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;
}
}
边栏推荐
猜你喜欢
随机推荐
《产品经理必读:五种经典的创新思维模型》的读后感
Lowcode: four ways to help transportation companies enhance supply chain management
Ray and OBB intersection detection
模拟Servlet的本质
【DesignMode】享元模式(Flyweight Pattern)
LeetCode 1186. 删除一次得到子数组最大和 每日一题
无法将“pip”项识别为 cmdlet、函数、脚本文件或可运行程序的名称
Prometheus API deletes all data of a specified job
skimage学习(2)——RGB转灰度、RGB 转 HSV、直方图匹配
Module VI
LeetCode 312. 戳气球 每日一题
null == undefined
Binary search tree (basic operation)
A tour of gRPC:03 - proto序列化/反序列化
正在准备面试,分享面经
最新高频Android面试题目分享,带你一起探究Android事件分发机制
【DesignMode】外观模式 (facade patterns)
skimage学习(1)
Personal notes of graphics (2)
"The" "PIP" "entry cannot be recognized as the name of a cmdlet, function, script file, or runnable program."