120. Triangle ---M

Given a triangle array, return the minimum path sum from top to bottom.

For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.

 

Example 1:

Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11
Explanation: The triangle looks like:
   2
  3 4
 6 5 7
4 1 8 3
The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).

Example 2:

Input: triangle = [[-10]]
Output: -10

 

Constraints:

• 1 <= triangle.length <= 200
• triangle[0].length == 1
• triangle[i].length == triangle[i - 1].length + 1
• -104 <= triangle[i][j] <= 104

 

Follow up: Could you do this using only O(n) extra space, where n is the total number of rows in the triangle?

A:

------------从下往上来计算-----利用一个数组来保持-----

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int numRow = triangle.size();
        vector<vector<int>> all(2, vector<int>());
        int indexAlternative = 0;
        // Initialize the last row
        for (int i = 0; i < triangle[numRow - 1].size(); i++) {
            all[indexAlternative].push_back(triangle[numRow - 1][i]);
        }
        for (int i = numRow - 2; i >= 0; i--) {
            vector<int>& lastList = all[indexAlternative];
            vector<int>& curList = all[1 - indexAlternative];
            vector<int>& triangleRow = triangle[i];
            // Clear current list
            curList.clear();
            for (int j = 0; j <= i; j++) {
                curList.push_back(triangleRow[j] +
                                  min(lastList[j], lastList[j + 1]));
            }
            indexAlternative = 1 - indexAlternative;
        }
        return all[indexAlternative][0];
    }
};

----------------------第二遍-----------------

不利用新的空间，就在原有的数据上更改。  从下到上，每次计算，某点到最下边的sum 的最小

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

Mistakes:
1: 因为i 是index， 所以，我们在上面的for(int j =0 ... )循环中， 应该是j<=i  而不是j<i
2: 第二遍的时候，因为，比较晕， 前天睡了4个小时，11点的时候，又补了1个小时。还是不清醒。 因此竟然忘记了第二层循环，哎~~~~~~~~~~


当我们在原有基础上更改的时候， 如果从上往下计算，需要注意的下标越界问题会比较tricky

public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int res = triangle.get(0).get(0);
        for(int i = 1;i<triangle.size();i++){
            List<Integer> p = triangle.get(i-1),  cur = triangle.get(i);
            res = Integer.MAX_VALUE; 
            for(int j=0;j<cur.size();j++){
                int minParentSum = (j==0? p.get(j) : (j==cur.size()-1? p.get(j-1) : Math.min(p.get(j), p.get(j-1)))   );
                cur.set(j, cur.get(j) + minParentSum);
                res = Math.min(res, cur.get(j));
            }
        }
        return res;
    }
}