微软面试题： LeetCode 120. 三角形最小路径和 出现次数：1

 解析：

        ,以上图的示例1为例，三角形 有 4 行。行号  0,1,2,3  ；最后一行每个数（4,1,8,3） 到三角形底部的路径就是其自身的值。

1.  定义状态  dp[i][j]   表示 元素 triangle[i][j] 到三角形底部的路径。

 2.  状态转移方程 ：dp[i][j] = min(dp[i-1][j], dp[i-1][j+1]) +  triangle[i][j] ；转态转移的方向是从下往上的。

3.  定义状态转移的起点： dp[n-1][k] =  triangle[n-1][k]  ，n 表示三角形的层数，k是最后一层的元素序号  ， 0<= k <= n-1。

4.  空间优化，分析状态转移方程，可以将转态数组，从二维压缩成一维 dp[i]   0<= i <= n-1。

代码：

class Solution {
public:
//时间 O(n^2)  空间  O(n)
    int minimumTotal(vector<vector<int>>& triangle)
    {
       int res = 0;
       const int h = triangle.size();
       vector<int> dp = triangle[h-1];//状态初始化
       for(int i = h -2; i >= 0 ;--i)//状态转移
       {
           for(int j = 0; j < i + 1;++j)
           {
               dp[j] = std::min(dp[j],dp[j+1]) + triangle[i][j];
           }
       }
       return dp[0];
    }
};