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