class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        //vector<vector<int>> ans(n+1,vector<int>(n+1));
        vector<int> ans(n+1);
        for(int i = n-1;i>=0;i--)
        {
            for(int j=0;j<=i;j++)
            {
                ans[j] = min(ans[j],ans[j+1])+triangle[i][j];
            }
        }
        return ans[0];
    }
};