“This is my 33rd day of participating in the First Challenge 2022. For details: First Challenge 2022”

[B] [C] [D]

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: The minimum sum of the top down paths of 2, 3, 4, 6, 5, 7, 4, 1, 8, 3 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

Advanced:

  • You can just use itO(n)Additional space (nIs the total number of rows of a triangle) to solve this problem?

Their thinking

The problem requires us to find the minimum path sum, that is, to find the maximum problem, and this result can be derived layer by layer, this familiar property, it is not a dynamic programming problem! 😎 excited heart, trembling hands, tao out to return to the three plate axe!

  1. State definition: In this case, there are two factors that affect the minimum path and result, one is the current row number and the other is the position of the number in the current row, so we can define two-dimensional DPdp[i][j]Represents the minimum path sum of the ith row subscript j position.
  2. Transfer equation: Subject specific mobile can only be given on the adjacent nodes, then in example 1, for example, 3 only from 2, 5 only from 3 or 4, 1 from 6 or 5, only because we require a shortest path and, so when you have two choices, we should choose the path and the smaller the point as the path in front of, Therefore, it can be deduced that:dp[i][j] = min(dp[i-1][j-1],dp[i-1][j])+triangle[i][j].
  3. Now it’s time to write code based on state definitions and transition equations!

Code implementation

Var minimumTotal = function(triangle) {var minimumTotal = function(triangle) {var minimumTotal = function(triangle) { i<len; I++) {dp [I] = []} dp [0] [0] = triangle [0] [0] / / traverse each layer, dp is derived for (let I = 1; i<len; Const n = triangle[I].length; for(let j = 0; j<n; If (j === 0) dp[I][0] = dp[I][0]+triangle[I][0] // if(j === 0) dp[I][0] = dp[I][0]+triangle[I][0] // if(j === 0) dp[I][0] = dp[I][0]+triangle[I][0] // So special handling else if (j) = = = n - 1 dp [I] [j] = dp [I - 1] [1] + triangle [I] [j] else dp [I] = [j] Math. Min (dp [I - 1] [1], dp [I - 1] [j]) + triangle [I] [j]}} / / returns the lowest value of the last layer of dp return math.h min (... dp[len-1]) };Copy the code

Optimizing spatial complexity

Var minimumTotal = function(triangle) {var minimumTotal = function(triangle) {var minimumTotal = function(triangle) { Dp [0] = triangle[0] = triangle[0] i<len; Const n = triangle[I].length; // Because the j of the current layer depends on j and j-1 of the previous layer, we need to deduce each layer from back to front for(let j = n-1; j>=0; J -) {/ / because j = 0 without a layer of j - 1, so special processing if dp (j = = = 0) [j] + = triangle [I] [j] / / because j is equal to n - no. 1 j, So special handling else if (j) = = = n - 1 dp [j] = dp] [j - 1 + triangle [I] [j] else dp [j] = math.h min (dp [1], dp [j]) + triangle [I] [j]}} / / returns the last layer Return math.min (... dp) };Copy the code

At this point we are done with Leetcode-120 – triangle minimum path sum

If you have any questions or suggestions, please leave a comment! 👏 🏻 👏 🏻 👏 🏻