120.md

Triangle

Description

link

---

Solution

• See Code

---

Code

Complexity T : O(n) M : O(n)

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        return self.dp(triangle, 0, len(triangle) - 1)[0]
        
    def dp(self, triangle, depth, m):
        if depth == m:
            return triangle[depth]
        last = self.dp(triangle, depth + 1, m)
        res = []
        for i, n in enumerate(triangle[depth]):
            res.append(n + min(last[i], last[i + 1]))
        return res