给了我们一个二维数组组成的三角形，让我们寻找一条自上而下的路径，使得路径和最短，要求从上一行到下一行只能走相邻的位置。要求空间复杂度O(n)。
[
[1],
[2,3],
[4,5,6],
[7,8,9,10]
]
肯定是个动归，首先想到的是用一个二维的dp数组，但是题目要求空间复杂度O(n)，所以用一维行不行呢？
这种题不熟练的时候可以先用一个二维的dp数组通过后，在再此基础上改成一维dp数组。
我们开辟一个大小为n的一维数组dp，然后从最顶层往最底层循环，若当前走完了第i层，dp[j]就代表以triangle[i][j]为终点的最短路径和。循环完所有层后，dp数组中的最小值即所求。
那我们如何更新dp呢？若现在刚进入第i层，则此时dp存放有第i-1层的结果，即以triangle[i-1][0, ..., i-1]为终点的最短路径，更新dp即求以triangle[i][0, ..., i]为终点的最短路径。首先来看第一个点triangle[i][0]，它只能从上一层的第一个点到达，例如上例的2->4，所以更新即dp[0] += triangle[i][0]；后面的话就有两个可能了：从上一层的靠左边和靠右边到达，例如上例的2->5和3->5，我们需要从中选取最短的路径。但是需要注意的是以2为终点的最短路径和已经被上一次修改dp所覆盖了，所以我们需要在每一次修改dp前用pre做备份。则更新表达式为dp[j] = triangle[i][j] + min(pre, dp[j])，pre表示上一层的dp[j-1]。这样一直更新知道这一层的最后一个点，与第一个点类似，只能从上一层最后一个点到达这个点。
时间复杂度O(n^2)， 空间复杂度O(n)
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int n = triangle.size();
vector<int>dp(n, 0);
dp[0] = triangle[0][0];
int pre, tmp;
for(int i = 1; i < n; i++){
pre = dp[0];
dp[0] += triangle[i][0]; // 第一个点
for(int j = 1; j < i; j++){
tmp = dp[j];
dp[j] = triangle[i][j] + min(pre, dp[j]);
pre = tmp;
}
dp[i] = pre + triangle[i][i]; // 最后一个点
}
int res = dp[0];
for(int i = 1; i < n; i++) res = min(res, dp[i]);
return res;
}
};