blob: d7e826b721ec342835d669b98af38d7984a3f108 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
#include "leetcode.h"
class Solution {
public:
int minimumTotal(vector<vector<int>> &triangle) {
vector<int> ans(triangle.size(), triangle[0][0]);
for (int i = 1; i < triangle.size(); i++)
for (int j = i; j >= 0; j--) {
if (j == 0)
ans[0] += triangle[i][j];
else if (j == i)
ans[j] = triangle[i][j] + ans[j - 1];
else
ans[j] = triangle[i][j] + min(ans[j - 1], ans[j]);
}
return *min_element(ans.begin(), ans.end());
}
};
int main() {}
|