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

triangle[i][j] = min(triangle[i - 1][j - 1], triangle[i - 1][j])

``````class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
for (int i = 1; i < triangle.size(); ++i) {
for (int j = 0; j < triangle[i].size(); ++j) {
if (j == 0) {
triangle[i][j] += triangle[i - 1][j];
} else if (j == triangle[i].size() - 1) {
triangle[i][j] += triangle[i - 1][j - 1];
} else {
triangle[i][j] += min(triangle[i - 1][j - 1], triangle[i - 1][j]);
}
}
}
return *min_element(triangle.back().begin(), triangle.back().end());
}
};
``````

``````class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
vector<int> dp(triangle.back());
for (int i = (int)triangle.size() - 2; i >= 0; --i) {
for (int j = 0; j <= i; ++j) {
dp[j] = min(dp[j], dp[j + 1]) + triangle[i][j];
}
}
return dp[0];
}
};
``````

-1

2   3

1  -1  -3

5   3   -1   2

DP：5  3  -1  2

DP：4  3  -1  2

DP：4  -2  -1  2

DP：4  -2  -4  2

DP：0  -2  -4  2

DP：0  -1  -4  2

DP：-2  -1  -4  2

https://leetcode.com/problems/triangle/

https://leetcode.com/problems/triangle/discuss/38730/DP-Solution-for-Triangle

https://leetcode.com/problems/triangle/discuss/38918/C%2B%2B-top-down-and-bottom-up-solutions.

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation