120. Triangle

120.cpp

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        if (triangle.empty()){
            return 0;
        }
        vector<int> dp (triangle.size()+1, INT_MAX);
        dp[1] = triangle[0][0];
        for (int i = 1; i < triangle.size(); ++i) {
            for (int j = i; j >= 0; --j) {
                dp[j+1] = min(dp[j], dp[j+1]) + triangle[i][j];
            }
        }
        return *min_element(dp.begin(), dp.end());
    }
};

int main(){
    vector<vector<int>> tri = {
            {2},
            {3, 4},
            {6, 5, 7},
            {4, 1, 8, 3}
    };
    Solution s;
    cout << s.minimumTotal(tri) << endl;
    return 0;
}