[C++/Python] LeetCode : Triangle

Question

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.

 

삼각형 배열이 주어지면 위에서 아래로 최소 경로 합계를 반환합니다.

각 단계마다 아래 행의 인접한 번호로 이동할 수 있습니다. 더 공식적으로 말하면, 현재 행의 인덱스 i에 있으면 다음 행의 인덱스 i 또는 인덱스 i 1로 이동할 수 있습니다.

 

제약사항

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

---

Solution

가능한 최선의 수행 시간(Best Conceivable Runtime(BCR)

• 모든원소를 한번 씩은 봐야하므로 O(n^2)

문제를 풀 때 고려한 사항

• 손으로 풀어보는 것이 도움이 될 때가 있다. 

---

Solution1 : DP

   2
  3 4
 6 5 7
4 1 8 3

위 예를 손으로 직접 풀이 해본다면, 

2

5, 6

11, 10, 13

15, 11, 18, 21

 

이런식이다.

즉 현재 원소의 까지의 path가 최소path라 가정한다면, path의 값은 현재 값 + 이전의 path값 2개 중 작은값을 더하는 것이 최소값이 된다. 그렇다면 이 값을 계속 기록해가며 본다면 가능한 모든 Path에서의 최소값을 구할 수 있다. 

 

다만 위에서 부터 차례로 합쳐 계산하는것 보다 아래서부터 올라가는 방식으로 min값을 구한다면, 더 쉽게 구할 수 있다. 

C++

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int last_row = triangle.size() - 1;

        for (int i = last_row - 1; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                triangle[i][j] = triangle[i][j] + min(triangle[i + 1][j], triangle[i + 1][j + 1]);
            }
        }

        return triangle[0][0];
    }
};

 

Python

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

        return triangle[0][0]

• Time complexity : O(n^2) 
• Space Complexity : O(n) 

출처 : https://leetcode.com/problems/triangle/description/?envType=study-plan-v2&envId=top-interview-150

Triangle - LeetCode