# LeetCode题目：Triangle，动态规划

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;
}
};
```

## “LeetCode题目：Triangle，动态规划”上的15条回复

macemers说：

macemers说：

O(2n) = O(n)

```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```
L说：

Annie说：

Will说：

Will说：

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