120.Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle [ [2], [3,4], [6,5,7], [4,1,8,3] ] The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note: Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int m = triangle.size();
        if(m < 1)   return 0;
        int n = triangle[m -1].size();
        vector<int> res(n, 0);
        res[0] = triangle[0][0];

        for(int i = 1; i < m; i++){

            for(int j = i; j >= 0; --j){
                if(j == i)  
                    res[j] = res[j - 1] + triangle[i][j];
                else if(j == 0)  
                    res[j] += triangle[i][j];
                else 
                    res[j] = min(res[j], res[j - 1]) + triangle[i][j];

            }
        }

        int min_step = INT_MAX;
        for(int i = 0; i < n; i++){
            min_step = std::min(min_step, res[i]);
        }
        return min_step;
    }
};

化简

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

        for(int i = n -2; i >= 0; i--){
            for(int j = 0; j <= i; j++){
                res[j] = std::min(res[j], res[j + 1]) + triangle[i][j];
            }
        }

        return res[0];
    }
};