Leetcode 120 Triangle
原题链接:
https://leetcode.com/problems/triangle/description/
方法一:
从上往下。
从第二行开始,比较每个元素肩上两个值的大小,取较小的值与该元素相加,和做为该位置的新值
triangle[i][j] = triangle[i][j] + min(triangle[i - 1][j], triangle[i - 1][j - 1]);
全部更新完之后,找出最后一行的最小值输出即可。
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int n = triangle.size(); //从顶至底
for(int i = 1; i < n; ++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], triangle[i - 1][j - 1]);
}
}
int res = triangle[n - 1][0];
for(int i = 1; i < triangle[n - 1].size(); ++i)
res = min(res, triangle[n - 1][i]);
return res;
}
};
方法二:
从下往上。
取最后一行做为dp初始值vector<int> dp(triangle.back())
dp数组中,比较相邻两个值,取较小的那个和他们头顶的元素相加做为新值,逐层向上,最后第一个元素即为所求。
class Solution {
public:
int minimumTotal(vector<vector<int> > &triangle) {
int n = triangle.size();
vector<int> dp(triangle.back());
for (int i = n - 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];
}
};