Topic address (120. Triangle minimum Path sum)

Leetcode-cn.com/problems/tr…

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 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). Example 2: Input: 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:

Can you just use O(n) of the extra space (n is the total number of rows of the triangle) to solve this problem?

Train of thought

In DP planning, each group of states is stored in DP array. The space optimization method is to remove the [-2] array and only save [-1] and the array traversed now for reduction

code

  • Language support: Python3

Python3 Code:


class Solution:
    def minimumTotal(self, triangle: List[List[int]]) - >int:
        cengNum = len(triangle)
        dp = []
        for i in range(cengNum):
            dp.append([0] *len(triangle[i]))
        dp[0] [0] = triangle[0] [0]
        for i in range(1,cengNum):
            cengList = triangle[i]
            for j,val in enumerate(cengList):
                ## Triangle side
                if j == 0:
                    dp[i][j] = dp[i-1][j]+val
                elif j == len(cengList)-1:
                    dp[i][j] = dp[i-1][j-1]+val
                else:# The center position is calculated by min
                    dp[i][j] = min(dp[i-1][j-1],dp[i-1][j])+val
        res = min(dp[-1])
        # print(dp)
        return res

if __name__ == '__main__':
    triangle = [[2], [3.4], [6.5.7], [4.1.8.3]]
    # triangle = [[-10]]
    res = Solution().minimumTotal(triangle)
    print(res)

Copy the code

Complexity analysis

Let n be the length of the array.

  • O(n2)O(n^2)O(n2)
  • Space complexity: O(n2)O(n^2)O(n2)