[동적계획법] 릿코드 Medium 120 'Triangle' (Python)

<문제 링크>

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

Triangle - LeetCode

---

<문제 풀이>

1. 삼각형의 꼭대기에서 바닥까지의 합을 구하는 것이므로, 아래 칸으로 이동할 때 윗 칸의 숫자를 더해준다.
2. 삼각형의 왼쪽 변의 숫자는 항상 왼쪽 숫자를 더하고, 오른쪽 변의 숫자는 항상 오른쪽 숫자를 더한다. 
3. 삼각형의 가운데 숫자들은 자신의 위의 숫자 2개에서 작은 값을 더하면 된다. 
4. 숫자를 다 더한 바닥의 숫자들 중 최솟값을 반환한다.

<코드>

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