triangle.cpp

#include <climits>
#include <vector>
#include <iostream>

using namespace std;

class Solution {
public:
    int minimumTotal(vector<vector<int> > &triangle) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        // vector<vector<int> > sums(triangle);
        // for (int i=0; i<sums.size(); i++) {
        // 	for (int j=0; j<sums[i].size(); j++) {
        // 		sums[i][j] = INT_MAX;
        // 	}
        // }
        // int result = 0;
        // result += minSum(triangle, 0, 0, sums);
        // return result;
        int m = triangle.size();
        for (int i=m-2; i>=0; i--) {
        	int n = triangle[i].size();
        	for (int j=i; j>=0; j--) {
        		triangle[i][j] += min(triangle[i+1][j], triangle[i+1][j+1]);
        	}
        }
        return triangle[0][0];
    }

    // int minSum(vector<vector<int> > &triangle, int row, int col, vector<vector<int> > sums) {
    // 	if (sums[row][col] < INT_MAX) return sums[row][col];
    // 	int subSum = 0;
    // 	if (row < triangle.size()-1)
    // 		subSum = min(minSum(triangle, row+1, col, sums), minSum(triangle, row+1, col+1, sums));
    // 	sums[row][col] = triangle[row][col] + subSum;
    // 	return sums[row][col];
    // }
};

int main (int argc, char *argv[]) {
	int my_ints[] = {1};
	int my_ints1[] = {2,3};
	std::vector<std::vector<int> > v;
	std::vector<int> v1(my_ints, my_ints+sizeof(my_ints)/sizeof(int));
	std::vector<int> v2(my_ints1, my_ints1+sizeof(my_ints1)/sizeof(int));
	v.push_back(v1);
	v.push_back(v2);
	Solution sol;
	cout << sol.minimumTotal(v) << endl;
	return 0;
}