1 /*[
2 [2],
3 [3,4],
4 [6,5,7],
5 [4,1,8,3]
6 ]
7
8
9 The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
10 */11 #include <iostream>
12 #include <vector>
13 #include <algorithm>
14 15 using namespace std;
16 17 class Solution {
18 public:
19 20 int minimumTotal(vector<vector<
int> > &triangle)
21 22 {
23 if (triangle.size() ==
1)
24 return triangle[
0][
0];
25 vector<vector<
int> >dp(triangle.size(), vector <
int> (triangle.size()));
26 for (
int i =
0; i < triangle.size(); ++i)
27 dp[triangle.size() -
1][i] = triangle[triangle.size() -
1][i];
28 for (
int i = triangle.size() -
2; i >=
0; --i)
29 {
30 for (
int j =
0; j <= i; ++j)
31 dp[i][j] = (dp[i +
1][j] < dp[i +
1][j +
1] ? dp[i +
1][j] : dp[i +
1][j +
1]) + triangle[i][j];
32 }
33 34 cout << dp[
0][
0] << endl;
35 return dp[
0][
0];
36 37 }
38 };
39 40 41 int main()
42 {
43 vector<vector<
int> >c = { { -
1 }, {
2,
3 }, {
1, -
1, -
3 } };
44 Solution A;
45 A.minimumTotal(c);
