120. Triangle.md

title	120. Triangle
Difficulty	Easy
tags	dp paths reverse

Problem : 120. Triangle

Method 1 : dp

reasoning

• can be seen as a variant of path problems with one destination, various starting points.
• the destination would be the head of the triangle
• the starting points would be the bases of the triangle
• steps of solving:
  • directly implement the scroll-list, initialize the dp array with the maximum size of triangle, with the elements of the bases. (starting points)

  vector<int> dp (n,0);
  for(int i = 0; i<n;i++) dp[i] = triangle[n-1][i];

  • then we loop from the bottom i=n-1 -> i=0.

  for(int i = n-1; i>0; i--)

  • and the answer would be $dp[0]$. (the definition of dp[i] here is the minimum sum of path at the element i in the scroll-list)

code

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        vector<int> dp (n,0);
        for(int i = 0; i<n;i++) dp[i] = triangle[n-1][i];
        for(int i = n-1; i>0; i--){
            for(int j=0 ; j<i; j++){
                dp[j] = min(dp[j],dp[j+1])+ triangle[i-1][j];
            }
        }
        return dp[0];
    }
};

complexity

Time

$O(n^2 /2)$

Space

$O(n)$