120. Triangle[M]

题目

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.

思路

如图分析：
$d(0,1) = Path[0,1] + min(d(1,1)，d(1,2))$

$d(1,1) = Path[1,1] + min(d(2,1),d(2,2))$

$d(1,2) = Path[1,2] + min(d(2,2),d(2,3))$

$……$

$d(3,1) = 4$

$d(3,2) = 1$

$d(3,3) = 8$

$d(3,4) = 3$

我们从底层往上走，每走一层，都是到这一层的最短路径距离。所以，我们每次只用保存到这一层每个元素的最短路径距离即可。也就是说，对于n层，我们最多只需要n个额外空间。

• 最底层: $[4,1,8,3]$
  
• 向上走:$[6+1,5+1,7+3] = [7,6,10]$
  
• 继续:$[3+6,4+6] = [9,10]$
  
• 最后:$[2+9] = [11]$
  

代码

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        vector <int> min_path(triangle.back());
        for(int i = triangle.size()-2;i>=0; i--)
        {
            for(int j = 0;j < triangle[i].size();j++)
            {
                min_path[j] = min(min_path[j],min_path[j+1]) + triangle[i][j];
            }
        }
        return min_path[0];
    }
};