# 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).

这题要求我们求出一个三角形中从顶到底最小路径和,并且要求只能使用O(n)的空间。

这题有两种解法,自顶向下以及自底向上。

首先来看自顶向下,根据题目我们知道,每向下一层,我们只能选择邻接数字进行累加,譬如上面第1行的数字3,它的下一行邻接数字就是6和5。

我们假设dp[m][n]保存了第m行第n个节点的最小路径和,我们有如下dp方程

+ `dp[m + 1][n] = min(dp[m][n], dp[m][n - 1]) + triangle[m + 1][n] if n > 0`
+ `dp[m + 1][0] = dp[m][0] + triangle[m + 1][0]`

因为只能使用O(n)的空间,所以我们需要滚动计算,使用一个一位数组保存每层的最小路径和,参考Pascal's Triangle,我们知道,为了防止计算的时候不覆盖以前的值,所以我们需要从后往前计算。

代码如下

```c++
class Solution {
public:
int minimumTotal(vector > &triangle) {
int row = triangle.size();
if(row == 0) {
return 0;
}

//初始化为最大值
vector total(row, INT_MAX);
total[0] = triangle[0][0];
int minTotal = INT_MAX;
for(int i = 1; i < row; i++) {
for(int j = i; j >= 0; j--) {
if(j == 0) {
total[j] = total[j] + triangle[i][j];
} else {
//上一层total[i]为INT_MAX,不会影响最小值
total[j] = min(total[j - 1], total[j]) + triangle[i][j];
}
}
}
for(int i = 0; i < row; i++) {
minTotal = min(minTotal, total[i]);
}
return minTotal;
}
};
```

区别于自顶向下,另一种更简单的做法就是自底向上了。dp方程为

`dp[m][n] = min(dp[m + 1][n], dp[m + 1][n + 1]) + triangle[m][n]`

我们仍然可以使用一位数组滚动计算。

代码如下

```c++
class Solution {
public:
int minimumTotal(vector > &triangle) {
if(triangle.empty()) {
return 0;
}
int row = triangle.size();
vector dp;
dp.resize(row);
//用最底层的数据初始化
for(int i = 0; i < dp.size(); i++) {
dp[i] = triangle[row-1][i];
}

for(int i = row - 2; i >= 0; i--) {
for(int j = 0; j <= i; j++) {
dp[j] = triangle[i][j] + min(dp[j], dp[j + 1]);
}
}
return dp[0];
}
};
```