Today's Challenge

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

Triangle - LeetCode

오랜만에 DFS 문제!
파스칼의 삼각형과 유사한 문제인 듯싶다.

(회식으로 인해 당일은 못 풀고 그 다음날 솔루션만 붙여 넣은 건 안 비밀... ㅠㅠ)

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        @cache
        def dfs(i, j):
            if i == len(triangle):
                return 0

            lower_left = triangle[i][j] + dfs(i + 1, j)
            lower_right = triangle[i][j] + dfs(i + 1, j + 1)

            return min(lower_left, lower_right)

        return dfs(0, 0)