120. triangle minimum path sum - Dynamic Planning

One 、 Title 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

Two 、 Problem solving

Dynamic programming

1、 State definition ：
dp[i][j] From point to point (i, j)(i,j) The minimum path to the bottom and .
2、 State shift ：
dp[i][j] = min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j]dp[i][j]=min(dp[i+1][j],dp[i+1][j+1])+triangle[i][j]

[2]
[3,4]
[6,5,7]
[4,1,8,3]

class Solution {
    
    public int minimumTotal(List<List<Integer>> triangle) {
    
        int length = triangle.size();
        // dp[i][j]  From point to point  (i, j)  The minimum path to the bottom and .
        int[][] dp = new int[length+1][length+1];
        for(int i = length-1;i>=0;i--){
    
            for(int j = 0;j<=i;j++){
    
                dp[i][j] = Math.min(dp[i+1][j],dp[i+1][j+1]) + triangle.get(i).get(j);
            }
        }
        return dp[0][0];
    }
}