This is the 22nd day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

Topic describes

Given a triangle triangle, find the minimum sum of paths from the top down.

Each step can only move to the next node in the next row. Adjacent nodes in this case are two nodes whose subscripts are the same or equal to the subscripts of the nodes at the previous level + 1. That is, if subscript I is right on the current row, then the next subscript can be moved to I or I + 1 on the next row.

  • Example 1:
Input: Triangle = [[2],[3,4],[6,5,7],[4,1,8,3]] Output: 11 Explanation: As shown in the diagram below: 2 3 4 6 5 7 4 1 8 3 The minimum sum of the top-down paths is 11 (i.e., 2 + 3 + 5 + 1 = 11).Copy the code
  • Example 2:
Triangle = [[-10]] Output: -10Copy the code
  • Tip:
1 <= triangle.length <= 200
triangle[0].length == 1
triangle[i].length == triangle[i - 1].length + 1
-104 <= triangle[i][j] <= 104
Copy the code

Implementation approach

We’re going to use dynamic programming to solve this problem, and we know that with dynamic programming we’re going to have to find an equation like dp(n)=min dp(n-1),dp(n-2)), so we’re going to find the rule, and we’re going to find the smallest path from the top of the triangle to the bottom, so we know that the top is a unique number, So let’s change the way we think about it and go from the bottom up to the top and take the smallest path, Triangle [I][j] = Math. Min (triangle[I +1][j] = Math. Min (triangle[I +1][j], Triangle [I + 1][j + 1]) + triangle[I][j], because the bottom row is certain, so if we go up we can take the smallest path and add them all the way to the top, and we can find the smallest path out of the top and triangle[0][0].

/ * * *@param {number[][]} triangle
 * @return {number}* /
var minimumTotal = function(triangle) {
    for(let i = triangle.length - 2; i >= 0; i--) {
        for (let j = 0; j < triangle[i].length; j++) {
            triangle[i][j] = Math.min(triangle[i + 1][j], triangle[i + 1][j + 1]) + triangle[i][j]
        }
    }
    return triangle[0] [0]};Copy the code