120. Triangle

Hint

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle)
    {
        // Initialize dp array with the last row of the triangle

        // Iterate from the second last row to the top row
        for ()
        {
            // Iterate through each element in the current row
            for ()
            {
                // Update dp[j] to be the current element plus the minimum of the two adjacent elements in the row below
            }
        }
        // dp[0] now contains the minimum path sum from the top to the bottom of the triangle
    }
};

Solution

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

• T:
  $O(N^2)$
• S:
  $O(N)$