For example, given the following triangle [ [2], [3,5], [7,5,8], [5,1,9,4] ]
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:
- Top Down approach
- Bottom Up approach
Solution in C++
#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; }
Output:
The minimum path sum from top to bottom using "top down" approach is = 6 The minimum path sum from top to bottom using "bottom up" approach is = 6