leetcode第一刷_Triangle

很簡單的一道DP，看到空間限制是O(N)的，不要習慣性的以為是要保存每一行的最小值，不難想到是要保存一行當中各個數為路徑終點時的和的大小。當算到最後一行時，就是從頂部到底部以這個底部位置為終點的最短路徑和，找一個最小的就可以了。

實現的時候要注意個問題，因為計算時要用到上一行的數據，所以為了避免數據被覆蓋，應該從後往前算，這個技巧用的很多，相信大家都很熟悉。

ac代碼如下：

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