Triangle Solutions in C++

// Source : https://oj.leetcode.com/problems/triangle/
// Author : Hao Chen
// Date   : 2014-06-18



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

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

class Solution {
public:
    int minimumTotal(vector<vector<int> > &triangle) {
        vector<int> steps;
        for (auto &v : triangle) {
            if (!steps.empty()) {
                v.front() += steps.front();
                v.back() += steps.back();
            }
            for (size_t i=1; i<steps.size(); ++i)
                v[i] += min(steps.at(i-1), steps.at(i));
            steps = v;
        }
        return *min_element(steps.cbegin(), steps.cend());
    }
};

/// Source : https://leetcode.com/problems/triangle/description/
/// Author : liuyubobobo
/// Time   : 2018-03-26

#include <iostream>
#include <vector>

using namespace std;

/// Dynamic Programming
/// Time Complexity: O(n^2)
/// Space Complexity: O(1)
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {

        int n = triangle.size();
        for(int i = 1 ; i < n ; i ++){

            triangle[i][0] += triangle[i-1][0];
            triangle[i][i] += triangle[i-1][i-1];
            for(int j = 1 ; j < i ; j ++)
                triangle[i][j] += min(triangle[i-1][j-1], triangle[i-1][j]);
        }

        return *min_element(triangle[n-1].begin(), triangle[n-1].end());
    }
};


int main() {

    vector<vector<int>> triangle = { {2},
                                     {3, 4},
                                     {6,5,7},
                                     {4,1,8,3}};
    cout << Solution().minimumTotal(triangle) << endl;
    // 11

    return 0;
}

/// Source : https://leetcode.com/problems/triangle/description/
/// Author : liuyubobobo
/// Time   : 2018-12-19

#include <iostream>
#include <vector>

using namespace std;

/// Memory Search
/// Time Complexity: O(n^2)
/// Space Complexity: O(1)
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {

        int n = triangle.size();
        vector<vector<int>> dp(n, vector<int>(n, -1));
        for(int i = 0 ; i < n ; i ++)
            go(triangle, n - 1, i, dp);

        return *min_element(dp[n-1].begin(), dp[n-1].end());
    }

private:
    int go(const vector<vector<int>>& triangle, int i, int j,
           vector<vector<int>>& dp){

        if(dp[i][j] != -1)
            return dp[i][j];

        if(i == 0)
            return dp[i][j] = triangle[i][j];

        if(j == 0)
            return dp[i][j] = triangle[i][j] + go(triangle, i - 1, 0, dp);

        if(j == i)
            return dp[i][j] = triangle[i][j] + go(triangle, i - 1, i - 1, dp);

        return dp[i][j] = triangle[i][j] + min(go(triangle, i - 1, j - 1, dp),
                                               go(triangle, i - 1, j, dp));
    }
};


int main() {

    vector<vector<int>> triangle = { {2},
                                     {3, 4},
                                     {6,5,7},
                                     {4,1,8,3}};
    cout << Solution().minimumTotal(triangle) << endl;
    // 11

    return 0;
}