Description

Submission

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

        vector<vector<int>> dp(m);
        dp[0].resize(1, triangle[0][0]);

        for(int i = 1; i < m; ++i) {
            dp[i].resize(i+1, INT_MAX);
            for(int j = 0; j < triangle[i].size(); ++j) {
                if(j == 0) dp[i][j] = dp[i-1][j] + triangle[i][j];
                else if(j == i) dp[i][j] = dp[i-1][j-1] + triangle[i][j];
                else dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j];
            }
        }

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