120. Triangle

Problem Statement

link: https://leetcode.com/problems/triangle/ https://leetcode.cn/problems/triangle/

Given a triangle array, return the minimum path sum from top to bottom.

For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.

Example:

Input: root = [1,2,3,4,5,null,7] Output: [1,#,2,3,#,4,5,7,#]

Input: root = [] Output: []

Solution Approach

The problem can be optimally solved using a bottom-up dynamic programming approach by updating each value in the triangle to the sum of itself and the minimum of the two adjacent values from the row below.

Algorithm

1. Start from the second to last row and move upwards, processing each row of the triangle.
2. For each element in the current row, add the minimum value between the two adjacent numbers in the row directly below.
3. After processing all rows, the topmost element of the triangle will contain the minimum path sum.

Implement

    class Solution:
  def minimumTotal(self, triangle: List[List[int]]) -> int:
      levels = len(triangle)
      for level in range(levels - 2, -1, -1):
          for i in range(len(triangle[level])):
              triangle[level][i] = triangle[level][i] + min(triangle[level + 1][i], triangle[level + 1][i + 1])
      return triangle[0][0]

    
    

Twitter  facebook  Email