Triangle — Bottom-Up 1D DP
Sanjeev SharmaAdvertisement
Problem
Find minimum path sum from top to bottom of triangle. Each step can move to adjacent numbers on the row below.
Approach — Bottom-Up 1D DP
Start from second-to-last row, update dp: dp[j] = triangle[i][j] + min(dp[j], dp[j+1]).
Time: O(n²) | Space: O(n)
Solutions
Python
class Solution:
def minimumTotal(self, triangle: list[list[int]]) -> int:
dp=triangle[-1][:]
for i in range(len(triangle)-2,-1,-1):
for j in range(len(triangle[i])):
dp[j]=triangle[i][j]+min(dp[j],dp[j+1])
return dp[0]
C++
class Solution {
public:
int minimumTotal(vector<vector<int>>& tri){
int n=tri.size(); vector<int> dp=tri.back();
for(int i=n-2;i>=0;i--)
for(int j=0;j<=i;j++) dp[j]=tri[i][j]+min(dp[j],dp[j+1]);
return dp[0];
}
};
Complexity
- Time: O(n²) | Space: O(n)
Advertisement
← Previous
Longest Common Subsequence — LCS 2D DP