Given a triangle, find the minimum path sum from top to bottom.

Given a triangle, find the minimum path sum from top to bottom. In each step you can only move to adjacent numbers on the row below.
For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
Follow up question:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

The solution for this problem can be solved in 2 ways:

1. Top Down approach
2. Bottom Up approach

Detailed explanation on how the code works, is given step by step in the solution code.

/*
* File     : triangle.cpp
*/

#include<iostream>
#include<vector>
using namespace std;


int top_down_solution(vector<vector<int>> &triangle)
{
  //take a result vector of size of triangle and initialize with INT_MAX
    vector<int> result(triangle.size(), INT_MAX);

    //initialize the first element of result with the value at triangle[0][0]
    result[0] = triangle[0][0];

    //now starting from the index 1, go through all the level
    for (int i = 1; i < triangle.size(); i++)
    {
      // this for loop represents the elements inside a level
        for (int j = i; j >= 1; j--)
        {
            result[j] = min(result[j - 1], result[j]) + triangle[i][j];
        }

        // as we are starting from index 1, add the elements from index 0 on all the level.
        result[0] += triangle[i][0];
    }

    //c++ library function to get the min element inside a vector.
    return *min_element(result.begin(), result.end());
}


/*
  In bottom up approach,
  1. Start form the row above the bottom row [size()-2].
  2. Each level add the smaller number of two numbers with the current element i.e triangle[i][j].
  3. Finally get to the top with the smallest sum.
*/
int bottom_up_solution(vector<vector<int>>& triangle) 
{
    vector<int> res = triangle.back();

    for (int i = triangle.size()-2; i >= 0; i--) 
        for (int j = 0; j <= i; j++) 
            res[j] = triangle[i][j] + min(res[j], res[j+1]);

    return res[0];
}

int main() 
{ 
    vector<vector<int> > triangle{  { 2 }, 
                                { 3, 9 }, 
                                { 1, 6, 7 } }; 
    cout <<"The minimum path sum from top to bottom using \"top down\" approach is = "<< top_down_solution(triangle)<<endl; 

    cout <<"The minimum path sum from top to bottom using \"bottom up\" approach is = "<< bottom_up_solution(triangle)<<endl; 


    return 0; 
}