120. Triangle - cocoder39/coco39_LC GitHub Wiki
2020 Notes:
top down recursion + cache
N is #elements in triangle. There are N subproblems and each subproblem takes O(1) time complexity so total time complexity is O(N). This problem can also be solved with using bottom-up DP: dp[n-1][j] = triangle[n-1][j], dp[i][j] = triangle[i][j] + min(dp[i+1, j], dp[i+1, j+1]
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
n = len(triangle)
memo = collections.defaultdict(dict)
def minPathSum(i, j):
if i == n-1:
return triangle[i][j]
if i in memo and j in memo[i]:
return memo[i][j]
memo[i][j] = triangle[i][j] + min(minPathSum(i+1, j), minPathSum(i+1, j+1))
return memo[i][j]
return minPathSum(0, 0)
========================================================================================
enumerate all case, can achieve O(1) memory by changing input vector. time is O(n ^ 2) and memory is O(n)
int minimumTotal(vector<vector<int>>& triangle) {
int n = triangle.size();
if (n == 0) {
return 0;
}
vector<int> dp = triangle[n - 1];
for (int i = n - 2; i >= 0; i--) {
int backup = dp[i + 1];
for (int j = triangle[i].size() - 1; j >= 0; j--) {
int tmp = triangle[i][j] + min(dp[j], backup);
backup = dp[j];
dp[j] = tmp;
}
}
return dp[0];
}