LeetCode 120. Triangle minimum path and daily question

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] <= 104

source ： 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;
    }
}