triangle.cpp

// 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 <iostream>
#include <vector>
using namespace std;

class Solution {
    
public:
    int minimumTotal(vector<vector<int> > &triangle) {
        vector< vector<int> > v;
        
        for (int i=0; i<triangle.size(); i++){
            
            if(i==0){
                v.push_back(triangle[i]);
                continue;
            }
            
            vector<int> tmp;
            
            
            for(int j=0; j<triangle[i].size(); j++){
                int x, y, z;
                x = y = z = 0x7fff;
                if ( (j-1) >= 0){
                    x = v[i-1][j-1];
                }
                if (j<v[i-1].size()) {
                    y = v[i-1][j];
                }
                /* won't take the previous adjacent number */
                //if ( (j+1)<v[i-1].size()) {
                //    z = v[i-1][j+1];
                //}
                tmp.push_back( min(x,y,z) + triangle[i][j] );
            }
            
            v.push_back(tmp);
            
        }
        int min=0x7fff;
        if (v.size() > 0){
            vector<int> &vb = v[v.size()-1];
            for(int i=0; i<vb.size(); i++){
                if (vb[i] < min ){
                    min = vb[i];
                }
            }
        }
           
        return min;
    }
private:
    inline int min(int x, int y, int z){
        int n = x<y?x:y;
        return (n<z?n:z);
    }
};


int main()
{
    vector< vector<int> > v;
    vector<int> 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;
}