题目

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

1
2
3
4
5
6
[
     [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.

大意

给定一个三角形，输出从顶到下面最短的路径，求出最短值。

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int results;
        vector<int> res(triangle.size(),0);
        int hang =triangle.size();
        for(int i=hang-1;i>=0;i--)
        {
            for(int j=0;j<=triangle[i].size()-1;j++)
            {
                 res[j] = min(res[j],res[j+1])+ triangle[i][j];
            }
        }
        return res[0];
    }
};

思路

因为是求最值，所以是典型的动态规划。

此题要求辅助空间为o(n).若采取从上往下的动态规划策略，需要两维的数组保存值。（再想想怎么感觉一维也行，但是更复杂，因为需要判断是否有左父亲节点和右父亲节点）

简单的动态规划，假如我们用minimus[i][j]来表示从第i行第j列处的数字开始往下到最后一层的最小路径和，那么有

1
minimus[i][j]=data[i][j]+min(minimums[i+1][j]+minimums[i+1][j+1])

然而上述描述中需要一个O（n^2）的额外空间，接下来我们来解决这个问题。

由于我们在公式里需要递归求解子问题，那么我们不妨反过来想一下，先求解子问题，然后再解决父问题。即，从下往上求解最小路径和。我们可以发现如下规律，当我们求解minimum[i][j]时，我们会用到minimum[i+1][j]和minimum[i+1][j+1]，但是当求解完所有minimum[i]之后minimum[i+1]就没有用处了。既然如此，我们可以复用同一个空间来存储minimum的值。进一步观察发现，存储最后一行的每个数字的最小路径和需要n个空间，因此至少我们需要n个空间，这也是题目里给出O（n）的空间复杂度的原因；之后存储倒数第二行时，我们只需要前面的n-1个空间……以此类推，第一行只需要一个空间来存储最小路径和，这也正是我们要求解的结果。

观察代码，先对最后一行进行赋值(最后一行的最小值就是三角形最后一行的值，这是动态规划的初始化赋值)

然后到达上一层后，求出到达倒数第二层中每个点的最小值，进行更新res,然后倒数第三层，以此类推。最后，到达的就是整体的最小值。