Leetcode: Triangle minimum path sum (Python)

A good function 2020-11-13 02:53:53
leetcode triangle minimum path sum

1. Title Description

Given a triangle , Find the smallest sum from the top down . Each step can only move to adjacent nodes in the next row .
for example , Given triangle ：

[
,
[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）.

explain ：

If you can just use O(n) Extra space （n Is the total number of rows of the triangle ） To solve this problem , So your algorithm is going to be a plus .

2. Ideas

Use dynamic planning , You can modify it directly on the original array , You can also use a length of n Of dp Array , To record .

2.1 Modify the original array directly

Modify from the bottom of the triangle up . Start from the penultimate layer and go up through the layers , For a certain layer , Modify all elements of this layer from scratch , Calculate each node plus the left and right child nodes （ Subpath ） The smaller value in , And put it into the current node . Modify layer by layer , Up to the first floor , After modifying the first layer , First floor （ node ） The element is the minimum path we require and .

2.2 Using an array , Do not modify the original data

Use an array to store the elements above the current layer , And then modify it from front to back dp Elements in an array .
dp[j] = triangle[i][j] + min(dp[j],dp[j+1]), among j Represents the level of the current layer j Subscripts of elements . Such a layer by layer modification dp The values in the array . Finally back to dp that will do . Different layers , Modified dp The number of elements in an array is also different .dp The array is initialized to the last data layer of the triangle .

2.2 python Code

class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
if len(triangle) == 0:
return 0
if len(triangle) == 1:
return triangle
dp = triangle[len(triangle)-1]
for row in range(len(triangle)-2,-1,-1):
for col in range(len(triangle[row])):
dp[col] = triangle[row][col] + min(dp[col],dp[col+1])
return dp