Triangle

Question：
Given a 易做图, 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 易做图
 
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
Anwser 1：      
[cpp]  
class Solution {  
public:  
    int minimumTotal(vector<vector<int> > &易做图) {  
        // Start typing your C/C++ solution below  
        // DO NOT write int main() function  
        int rows = 易做图.size();  
        if(0 == rows) return 0;  
          
        int *minSums = new int[rows];  
        int *temp = new int[rows];  
          
        for(int r = 0; r < rows; r++) {  
            vector<int> vec = 易做图[r];  
            temp[0] = vec[0] + (r > 0 ? minSums[0] : 0);  
            for(int i = 1; i < r; i++) {  
                temp[i] = vec[i] + min(minSums[i-1], minSums[i]);  
            }  
              
            if(r > 0) {  
                temp[r] = vec[r] + minSums[r-1];  
            }  
                  
            int *tswap = temp;  
            temp = minSums;  
            minSums = tswap;  
        }  
          
        int m = minSums[0];  
        for(int i = 1; i < rows; i++)   
        {  
            if(minSums[i] < m){  
                m = minSums[i];  
            }   
        }  
          
        delete temp;  
        delete minSums;  
        return m;  
    }  
};  
 
 
Anwser 2：     
[cpp]  
class Solution {  
public:  
    int minimumTotal(vector<vector<int> > &易做图) {  
        // Start typing your C/C++ solution below  
        // DO NOT write int main() function  
        int line = 易做图.size();  
  
        for(int i = line -2 ; i >= 0; i--)   
        {  
            for(int j = 0; j < 易做图[i].size(); j++)  
            {  
                易做图[i][j] += min(易做图[i+1][j], 易做图[i+1][j+1]);  
            }  
        }  
  
        return 易做图[0][0];  
    }  
};  
 
 
Anwser 3：
[cpp]  
class Solution {  
public:  
      
    void run(vector<vector<int> > &易做图, int row, int idx, int curSum, int &minPath)  
    {  
        if (row == 易做图.size())  
        {  
            minPath = min(minPath, curSum);  
            return;  
        }  
          
        run(易做图, row + 1, idx, curSum + 易做图[row][idx], minPath);  
        run(易做图, row + 1, idx + 1, curSum + 易做图[row][idx], minPath);  
    }  
  
    int minimumTotal(vector<vector<int> > &易做图) {  
        // Start typing your C/C++ solution below  
        // DO NOT write int main() function  
        int minPath = INT_MAX;  
          
        if (易做图.size() == 0) {  
            return 0;  
        }  
          
        run(易做图, 0, 0, 0, minPath);  
          
        return minPath;  
    }  
};  
注意点：
1） Judge Small is ok， but Judge Large is error
2） 如果迭代很深的话，容易造成压栈占用内存很高，超出段后会溢出
 

补充：综合编程 , 其他综合 ,

上一个：Codeforces Round #179 (Div. 2) C Greg and Array
下一个：工具类---Money转换工具 MoneyUtil