Triangle

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.

Solution:

Viterbi algorithm. Starting from the bottom level and eliminate the paths with higher weight.

No extra space needed if we can change the original triangle.

O(n) extra space needed if we cannot change the original triangle.

The following codes pass LeetCode Online Large Judge.

No extra space needed:

class Solution {
public:
    int minimumTotal(vector<vector<int> > &triangle) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        for(int i = triangle.size() - 1; i > 0; i--) {
            for(int j = 0; j < triangle[i - 1].size(); j++) {
               triangle[i-1][j] =
                    min(triangle[i-1][j] + triangle[i][j]
                    ,triangle[i-1][j] + triangle[i][j+1]); 
            }
        }
        return triangle[0][0];
    }
};

O(n) extra space needed:

class Solution {
public:
    int minimumTotal(vector<vector<int> > &triangle) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<int> tmp_chk = triangle[triangle.size() - 1];
        for(int i = triangle.size() - 1; i > 0; i--) {
            for(int j = 0; j < triangle[i - 1].size(); j++) {
               tmp_chk[j] =
                    min(triangle[i-1][j] + tmp_chk[j]
                    ,triangle[i-1][j] + tmp_chk[j+1]);
            }
        }
        return tmp_chk[0];
    }
};