January 21, 2025
Today I start working on multidimensional DP. I expect these problems to require a dynamicly-sized array to build a solution, rather than a static number of variables. I chose to write about this problem because it is a great example of how we can think of a problem from the bottom up to build an optimal solution.
1class Solution:2 def minimumTotal(self, triangle: List[List[int]]) -> int:3 rows = len(triangle)4 memo = triangle[-1][:]5 for row in range(rows - 2, -1, -1):6 for col in range(row + 1):7 memo[col] = min(memo[col], memo[col + 1]) + triangle[row][col]8 return memo[0]
Time complexity is O(n) and space complexity is O(n).
LeetCode 34. Find First and Last Position of Element in Sorted Array
LeetCode 1004. Max Consecutive Ones III