leetcode medium : Triangle

https://leetcode.com/problems/triangle/description/

Triangle - LeetCode

 

일단 그냥 나이브하게 탑다운 dp로 풀면 다음과 같다.

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        memo = {}

        def dp(i, j):
            if i == len(triangle):
                return 0

            if (i, j) in memo:
                return memo[(i, j)]

            leftmin = dp(i + 1, j)
            rightmin = dp(i + 1, j + 1)

            result = min(leftmin, rightmin) + triangle[i][j]
            memo[(i,j)] = result
            return result

        return dp(0, 0)

 

근데 이게 문제의 팔로우업 조건을 만족하나?

공간복잡도가 O(n)이 아니다. (n은 row 수)

잘 생각해보면 한 row의 minimumTotal을 계산하는데에는 그 다음 row의 minimumTotal만 알고있으면 되니까

한 번에 한 row만 가지고 있으면 된다.

아니, 인풋으로 들어온 리스트를 수정할수만 있으면 extra space가 필요가 없다. (근데 그렇겐 하지 말자)

 

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        dp = triangle[-1]
        i = -2

        while len(dp) != 1:
            dp = [min(dp[j], dp[j + 1]) + triangle[i][j] for j in range(len(dp) - 1) ]
            i -= 1

        return dp[0]

EASY