非常easy的一道DP，看到空间限制是O(N)的，不要习惯性的以为是要保存每一行的最小值，不难想到是要保存一行其中各个数为路径终点时的和的大小。当算到最后一行时，就是从顶部究竟部以这个底部位置为终点的最短路径和，找一个最小的就能够了。

实现的时候要注意个问题，由于计算时要用到上一行的数据，所以为了避免数据被覆盖，应该从后往前算，这个技巧用的非常多，相信大家都非常熟悉。

ac代码例如以下：

class Solution {

public:

    int minimumTotal(vector<vector<int> > &triangle) {

        int lines = triangle.size();

        if(lines == 0)  return 0;

        vector<int> res(lines, 0);

        for(int i=0;i<lines;i++){

            if(i>0)

                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<lines;i++){

            if(res[i]<mmin)

                mmin = res[i];

        }

        return mmin;

    }

};