Shulou(Shulou.com)06/01 Report--

This article is to share with you about how to find the minimum path sum of triangles with golang leetcode skills. The editor thinks it is very practical, so share it with you as a reference and follow the editor to have a look.

Triangle minimum path sum

Given a triangle, find the minimum path sum from top to bottom. Each step can only be moved to the adjacent nodes in the next row.

Here, adjacent nodes refer to two nodes whose subscript is the same as or equal to the subscript + 1 of the node above.

For example, give a triangle:

[

[2],

[3,4]

[6,5,7]

[4,1,8,3]

]

The sum of the smallest paths from top to bottom is 11 (that is, 2 + 3 + 5 + 1 = 11).

Description:

If you can only use the extra space of O (n) (n is the total number of rows of triangles) to solve this problem, then your algorithm will get a lot of points.

Ideas for solving the problem:

1, for the position [iMagnej], whether we choose [iQuin1JEI] or [iLife1JOJE1] depends on

Sum (iPhone1) and sum (iLife1)

2. Recursion can be solved, but it is not optimal.

3. Dynamic programming

Line A, line I depends on line I + 1, so let's dp [I] [j] = min (DP [I + 1] [j], dp [I / I] [j]) + triangle [I] [j]

B, in order to reduce the space complexity, our line I result directly covers line I + 1.

Code implementation: 1 Recursion

Func minimumTotal (triangle [] int) int {if len (triangle)

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.