//120. Triangle
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).

#include <iostream>
#include <vector>
#include <cassert>
#pragma GCC diagnostic error "-std=c++11"
using namespace std;

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        assert(triangle.size()>0);

        int m=triangle.size();
        vector<vector<int>> dp(m,vector<int>(m,triangle[0][0]));

        //i begin 1 i-1 != -1
        for(int i=1;i<m;i++){
            for(int j=0;j<=i;j++){
                if(j==0){
                    dp[i][0]=dp[i-1][0]+triangle[i][0];
                } else if(j==i){
                    dp[i][j]=dp[i-1][i-1]+triangle[i][j];
                } else{
                    dp[i][j]=min(dp[i-1][j],dp[i-1][j-1])+triangle[i][j];
                }
            }
        }
        //dp last level min
        int res=dp[m-1][0];
        for(int j=1;j<triangle[m-1].size();j++){
            res=min(res,dp[m-1][j]);
        }

        return res;


    }
};

int main(){

    int arr1[]={2};
    int arr2[]={3,4};
    int arr3[]={6,5,7};
    int arr4[]={4,1,8,3};
    vector<int> vec1(arr1,arr1+sizeof(arr1)/sizeof(int));
    vector<int> vec2(arr2,arr2+sizeof(arr2)/sizeof(int));
    vector<int> vec3(arr3,arr3+sizeof(arr3)/sizeof(int));
    vector<int> vec4(arr4,arr4+sizeof(arr4)/sizeof(int));

    vector<vector<int>> triangle;
    triangle.push_back(vec1);
    triangle.push_back(vec2);
    triangle.push_back(vec3);
    triangle.push_back(vec4);

    cout<<Solution().minimumTotal(triangle)<<endl;
    return 0;
}