120. Triangle

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.

---

给一个数字三角形，求从顶到底的最小路径和，很常规的DP题，要求只用O(n)的空间，思路和LeetCode Pascal’s Triangle II有点类似，即从后往前算。 把题目中的三角形推到左边，成下面的样子：

[2],
[3,4],
[6,5,7],
[4,1,8,3]
可以看到除了首尾两个元素，其他元素的递推公式为：dp[col]=min(dp[col-1],dp[col])+triangle[row][col]，首尾元素只能从其上面的一个元素下来，所以只有一条路。完整代码如下：

class Solution {
public:
    int minimumTotal(vector<vector<int> >& triangle)
    {
        vector<int> dp(triangle.size(), 0);
        dp[0] = triangle[0][0];
        for (int row = 1; row < triangle.size(); row++) {
            dp[row] = dp[row – 1] + triangle[row][row];
            for (int col = row – 1; col > 0; col–) {
                dp[col] = min(dp[col – 1], dp[col]) + triangle[row][col];
            }
            dp[0] = dp[0] + triangle[row][0];
        }
        return *min_element(dp.begin(), dp.end());
    }
};

本代码提交AC，用时6MS。