// Source : https://oj.leetcode.com/problems/triangle/
// Author : Hao Chen
// Date : 2014-06-18
/**********************************************************************************
*
* Given a triangle, find the minimum path sum from top to bottom.
* Each step you may 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).
*
* Note:
* 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.
*
*
**********************************************************************************/
#include
#include
using namespace std;
class Solution {
public:
int minimumTotal(vector > &triangle) {
vector< vector > v;
for (int i=0; i tmp;
for(int j=0; j= 0){
x = v[i-1][j-1];
}
if (j 0){
vector &vb = v[v.size()-1];
for(int i=0; i > v;
vector i;
i.push_back(-1);
v.push_back(i);
i.clear();
i.push_back(2);
i.push_back(3);
v.push_back(i);
i.clear();
i.push_back(1);
i.push_back(-1);
i.push_back(-3);
v.push_back(i);
Solution s;
cout << s.minimumTotal(v) << endl;;
v.clear();
i.clear();
i.push_back(-1);
v.push_back(i);
i.clear();
i.push_back(3);
i.push_back(2);
v.push_back(i);
i.clear();
i.push_back(-3);
i.push_back(1);
i.push_back(-1);
v.push_back(i);
cout << s.minimumTotal(v) << endl;;
return 0;
}