Triangle (C++ code)

Leetcode Triangle Oct 30 '123620 / 9772
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.


好久没写code了，先练个暴力的：

void helper(vector<vector<int> > &triangle, int &res, int sum, int level, int pos){
  if(level == triangle.size()) {
        if(sum < res) res = sum;
        return;
  }
  helper(triangle, res, sum + triangle[level][pos], level + 1, pos);
  helper(triangle, res, sum + triangle[level][pos+1], level + 1, pos + 1);

}

int minimumTotal(vector<vector<int> > &triangle) {
        int  n = triangle.size();
        if(n == 0) return 0;
        int sum = triangle[0][0], res = INT_MAX;
        helper(triangle,res, sum, 1,0);

        return res;
    }

果然大集合没过，想了下，如果记录到达每个node的最短距离，可以省去很多重复计算，于是写了下面这个：
 int minimumTotal(vector<vector<int> > &triangle) {
       int  n = triangle.size();
       map<pair<int,int>, int> record;
       int res = INT_MAX;
       record[make_pair(0,0)] = triangle[0][0];
       for(int i = 1; i < n; i ++){
            record[make_pair(i,0)] = record[make_pair(i-1,0)] + triangle[i][0];
            record[make_pair(i,i)] = record[make_pair(i-1,i-1)] + triangle[i][i];
            for(int j = 1;  j < i; j++){
                 record[make_pair(i,j)] = min(record[make_pair(i-1,j)], record[make_pair(i-1, j-1)]) +  
                 triangle[i][j];
            }
      }     
      for(int i = 0; i < n; i++){
        if(record[make_pair(n-1,i)] < res) res = record[make_pair(n-1,i)];
      }
        return res;
    }

然后又follow了一下题目的hint, 只用一个长度为n的array来记录结果。注意每次新的一行更新要倒着来。
 int minimumTotal(vector<vector<int> > &triangle) {
       int  n = triangle.size();
      vector<int> record(n, INT_MIN);
       int res = INT_MAX;
       record[0] = triangle[0][0];
       for(int i = 1; i < n; i ++){
            record[i] = record[i-1] + triangle[i][i];
            for(int j = i-1;  j > 0; j--){
                 record[j] = min(record[j], record[j-1]) +  triangle[i][j];           
            }
            record[0] += triangle[i][0];
      }     
      for(int i = 0; i < n; i++){
        if(record[i] < res) res = record[i];
      }
        return res;
    }