**Solution**

**Triangle** https://leetcode.com/problems/triangle/?tab=Description

**Memoization**

- f[n,i] = min(f[n+1,i], f[n+1,i+1]) + mat[n,i] for n <= N-1
- return 0 for n=N
- For space of order N, we can use a DP solution where we store the minimum sum for every index. We do not require information of previous rows.

```
from collections import defaultdict
class Solution(object):
def helper(self, triangle, row, col, cache):
N = len(triangle)
if row == N:
return 0
if row in cache and col in cache[row]:
return cache[row][col]
cache[row][col] = min(self.helper(triangle, row+1, col, cache), self.helper(triangle, row+1, col+1, cache)) + triangle[row][col]
return cache[row][col]
def minimumTotal(self, triangle):
"""
:type triangle: List[List[int]]
:rtype: int
"""
return self.helper(triangle, 0, 0, defaultdict(dict))
```