LeetCode - 120. Triangle (python)

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

• 난이도: medium
• 알고리즘: dynamic programming

접근방법

• 삼각형의 i행, j열에 도달하는 경로를 생각해 본다
• j가 0인 경우(가장 첫 번째 열)
  • (i - 1)행의 0번째 열으로부터 오는 경우만 존재
• j가 i인 경우(가장 마지막 열)
  • (i - 1)행의 (i - 1)번째로 부터 오는 경우만 존재
• 위 두 경우가 아닌 경우
  • (i - 1)행 (j - 1)열에서 오는 경로, j열에서 오는 경로 두 가지 존재
  • 점화식을 세워보면 다음과 같다
  • path[i][j] = min(path[i - 1][j - 1], path[i - 1][j]) + triangle[i][j]

소스코드

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        n = len(triangle)

        if n == 1:
            return triangle[0][0]

        cache = [[0 for _ in range(n)] for _ in range(n)]
        cache[0][0] = triangle[0][0]

        for i in range(1, n):
            for j in range(i + 1):
                if j == 0:
                    cache[i][j] = cache[i - 1][j] + triangle[i][j]
                elif j == i:
                    cache[i][j] = cache[i - 1][j - 1] + triangle[i][j]
                else:
                    cache[i][j] = min(cache[i - 1][j - 1], cache[i - 1][j]) + triangle[i][j]

        return min(cache[n - 1])