# LeetCode题目：Triangle，动态规划

By | 2012 年 10 月 31 日

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.

```class Solution {
public:
int minimumTotal(vector > &triangle) {
int rows = triangle.size();
if(0 == rows) return 0;
int *minSums = new int[rows];
int *temp = new int[rows];

for(int r = 0; r < rows; ++r) {
vector trow = triangle[r];
if(trow.size() != r + 1) return 0;//input error occur
//first should be last 0 add trow[0]
temp[0] = trow[0] + (r > 0 ? minSums[0] : 0);
//from 1 to r - 1, the min from above to parants add self
for(int i = 1; i < r; ++ i) {
temp[i] = trow[i] + min(minSums[i-1],minSums[i]);
}
//last element, just like the first one. only can add self to the last element above.
if(r > 0)
temp[r] = trow[r] + minSums[r-1];
//swap temp with minSums
int *tswap = temp;
temp = minSums;
minSums = tswap;
}

//scan the minSums, find out the minimum one
int m = minSums[0];
for(int i = 1; i < rows; ++i) {
if(minSums[i] < m)
m = minSums[i];
}

delete temp;
delete minSums;
return m;
}
};
```

Code rewrite at 2012-12-30

```class Solution {
public:
int minimumTotal(vector > &triangle) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int levels = triangle.size();
if(levels<=0) return 0;
vector *psum = new vector(levels,0);
vector *psumtemp = new vector(levels,0);
(*psum)[0] = triangle[0][0];
for(int ilevel = 1; ilevel < levels; ++ilevel) {
vector &level = triangle[ilevel];
const int levelsize = level.size();
//only one path could arrive to the first and last number in a level
(*psumtemp)[0] = (*psum)[0] + level[0];
//if (level.size() > 1)
(*psumtemp)[levelsize - 1] = (*psum)[levelsize - 2] + level[levelsize - 1];
//there are 2 pathes for the middle numbers.
for(int ipos = 1; ipos < levelsize - 1; ++ipos) {
int tsum = (*psum)[ipos] + level[ipos];
if(tsum > (*psum)[ipos-1] + level[ipos]) {
tsum = (*psum)[ipos-1] + level[ipos];
}
(*psumtemp)[ipos] = tsum;
}
//swap the psum and psumtemp
vector *ptemp = psum;
psum = psumtemp;
psumtemp = ptemp;
}
//scan the psum and output the minnimum sum
int minsum = (*psum)[0];
for(int i = 1; i < levels; ++i) {
if(minsum > (*psum)[i])
minsum = (*psum)[i];
}
//clearup
delete psum;
delete psumtemp;
return minsum;
}
};
```

Code rewrite at 2013-1-17

```class Solution {
public:
int minimumTotal(vector > &triangle) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int rows = triangle.size();
if(0 == rows) return 0;//error
int *sumrow = new int[rows];
int *sumrowtemp = new int [rows];
sumrow[0] = triangle[0][0];
for(int ir = 1; ir < rows; ++ir) {
vector &trirow = triangle[ir];
sumrowtemp[0] = sumrow[0] + trirow[0];
for(int ic = 1; ic < trirow.size(); ++ic) {
int minsum = sumrow[ic-1];
if(ic < trirow.size()-1 && sumrow[ic] < minsum) {
minsum = sumrow[ic];
}
sumrowtemp[ic] = minsum + trirow[ic];
}
int *temp = sumrow;
sumrow = sumrowtemp;
sumrowtemp = temp;
}
int ret = sumrow[0];
for(int ic = 1; ic < rows; ++ic) {
if(ret > sumrow[ic]) ret = sumrow[ic];
}
delete sumrow;
delete sumrowtemp;
return ret;
}
};
```

## 15 thoughts on “LeetCode题目：Triangle，动态规划”

1. macemers

楼主你好，

想请问，两次的code rewrite比起第一次有哪些改进的地方？另外题目有个bonus要O(n)的空间，似乎都没有达到？

全部解法都是开了两个O(n)的空间的数组

1. uniEagle Post author

算法上本身没有什么改进，只在循环次数和边界上稍有变化。最开始那个版本是整个三角循环的，后面两次都是从第二行开始的。
另外其实常数倍O(n)还是O(n)。

1. macemers

题目上写“using only O(n) extra space, where n is the total number of rows in the triangle.”

难道不是指，只用一个长度为n的数组吗？

2. haiyyang

根据你开头动归的提示，我的代码是这样的，嘿嘿 ：

```class Solution {
public:
int minimumTotal(vector &triangle) {
if(triangle.empty())return 0;

int max=triangle.back().size();
vector dp(triangle.back().begin(),triangle.back().end()); //最后一行拷贝到额外空间，并作为动态规划的表格

for(int i=triangle.size()-2;i>=0;i--)
{
int s=triangle.at(i).size();
for(int j=0;j

```
3. Annie

其实由下到上遍历更方便，就不需要两个一维数组互相切换了。

4. Will

是的，我题理解错了，忘了得相邻的上下两数才能构成path。
谢谢！

5. Will

能否请教下这个的时间复杂度是不是O(n^2)? n为rows 如果n为一共多少个数的话，应该是O(n)。
那能否用找出每行的最小值，然后从而遍找到path的方法呢？
谢谢！！！

1. uniEagle Post author

恩，如果按照题目中n定义为总的行数的话，时间复杂度是O(n^2)的。
找出每行最小，加起来的方法不正确，如果你看这棵树的话就知道了：

```[
[2],
[3,4],
[6,5,2],
[1,5,8,3]
]
```

这棵树的最小值并不是(2+3+2+1 = 8)