# Leetcode 120. Triangle

## 題解

### DP


#### 狀態轉移方程

nums[y][x] = min(nums[y-1][x],nums[y-1][x-1]) + nums[y][x]

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        # Time coomplexity: O(n ** 2)
        # Space complexity: O(1)
        n = len(triangle)
        for y in range(1,n):
            nums = triangle[y]
            n = len(nums)
            for x in range(n):
                num = nums[x]
                prev_n = len(triangle[y-1])
                prev = 10 ** 4
                if 0 <= x-1 < prev_n:
                    prev = min(prev,triangle[y-1][x-1])
                if 0 <= x < prev_n:
                    prev = min(prev,triangle[y-1][x])
                nums[x] = prev + num
        return min(triangle[n-1])