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.

//审题很重要，一开始理解错了题意，觉得题里说的Adjacent Number是指相邻的row，只要找到每行里最小的值，把他们相加就可以了。结果错了。
//第二次发现觉得可以用djisktra来解。 维护一个最小堆。但这个堆的大小达到了n^2，n为行数，仍然不满足题意。
//第三次发现用一个优化节省空间的动态规划可解，n[i]表示到达某行第i列所需的最小花费。
//此题和图里的最短路不同在于，这个三角矩阵到达某一点的最短花费可以在遍历它之前所有行之后得到，但在图里却无法得到到达某一点的最短花费，除非遍历了整个图。
//这里又来了一个tricky的地方。因为它是一个三角矩阵，相邻行的元素放置位置有错位，所以Adjacent Number指的是上一行同列和上一行列数-1的元素。而不是我们一厢情愿地以为的，是同列，同列+1，同列-1.切记
//think it loud，当面试时，一定要问清面试官该题的所有detail，确定自己理解了题意后再敲代码。
class Solution {
public:
    int minimumTotal(vector<vector > &triangle) {
        int re;
        if(triangle.empty() == true){
            return 0;
        }
        else{
            size_t nrows = triangle.size();
            int n[nrows];
            memset(n, 0, sizeof(int) * nrows);
            n[0] = triangle[0][0];
            for(int i = 1; i < nrows; i++){
                int lastElement;
                for(int j = 0; j <= i; j++){
                    if(j == 0){
                        lastElement = n[j];
                        n[j] = triangle[i][j] + n[j];  
                    }   
                    else if(j == i){
                        n[j] = triangle[i][j] + lastElement;
                    }
                    else {
                        int tmp = n[j];
                        n[j] = triangle[i][j] + min(n[j], lastElement);
                        lastElement = tmp;
                    }
                }
            }
            re = n[0];
            for(int i = 0; i < nrows; i++){
                if(n[i] < re){
                    re = n[i];
                }
            }
            return re;
        }
    }
};