leetcode-120-三角形最小路径和

 

class Solution {

public:

    int minimumTotal(vector<vector<int>>& triangle) {

        int res = INT_MAX;

        vector<vector<int>> dp;

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

        for (int i=1; i<triangle.size(); i++){

            dp.push_back(vector<int> (i+1));

            for (int j=0; j<triangle[i].size(); j++){

                if (j == 0) dp[i][j] = dp[i-1][0]+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] + triangle[i][j], dp[i-1][j] + triangle[i][j]);

            }

        }

        for (auto i:dp[dp.size()-1]) res = min(res, i);

        return res;

    }

};