120. Triangle

Description

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 1:

• Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
• Output: 11
• Explanation: The triangle looks like:
        2
      3 4
    6 5 7
  4 1 8 3
  The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).

Example 2:

• Input: triangle = [[-10]]
• Output: -10

Constraints:

• 1 <= triangle.length <= 200
• triangle[0].length == 1
• triangle[i].length == triangle[i - 1].length + 1
• -10⁴ <= triangle[i][j] <= 10⁴

Follow up: Could you do this using only O(n) extra space, where n is the total number of rows in the triangle?

Submitted Code

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        rows = len(triangle)
        for row in range(rows-2, -1, -1):   # 마지막에서 2번째 행에서 시작
            cols = len(triangle[row])
            for col in range(cols):
                # 아래 행에서 인접한 두 값 중 더 작은 값을 현재 값에 더해서 갱신
                triangle[row][col] += min(triangle[row+1][col], triangle[row+1][col+1])

        return triangle[0][0]               # 최소 경로 합

Runtime: 0 ms | Beats 100.00%
Memory: 20.18 MB | Beats 45.90%

마지막에서 2번째 행부터 시작하여 맨 위까지 거꾸로 올라가는 방법이다.

Other Solutions

1st

class Solution:
    def minimumTotal(self, t: List[List[int]]) -> int:
        n=len(t)
        for i in range(1, n):
            t[i][0]+=t[i-1][0]
            t[i][i]+=t[i-1][i-1]
            for j in range(1, i):
                t[i][j]+=min(t[i-1][j], t[i-1][j-1])
        return min(t[-1])
        

time complexity: 𝑂(𝑛²) ← n(n+1)/2개
space complexity: 𝑂(1)

위에서 2번째 행부터 맨 마지막까지 정방향으로 내려갈 수도 있다.