很简单的一道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;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