// 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; }