leetcode-triangle

虽说题目很简单，也没有优化。但是depend on myself & 一遍就AC还是很让人开心的。。

之前二维vector不熟，通过这个题熟了很多。

时间复杂度O(n^2),空间复杂度O(n^2). 优化之后可以做到空间复杂度O(1), 见代码2.

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 class Solution {
 7 public:
 8     int minimumTotal(vector<vector<int> > &triangle) {
 9         if (triangle.empty())
10             return 0;
11         vector<vector<int>> d;
12         for (int i = 0; i < triangle.size(); i++)
13         {
14             d.push_back(vector<int>(triangle[i].size(), INT_MAX));
15         }
16         d.at(0).at(0) = (triangle.at(0).at(0));
17         for (int i = 1; i < triangle.size(); i++)
18         {
19             for (int j = 0; j < triangle[i].size(); j++)
20             {
21                 if (j == 0)
22                 {
23                     d.at(i).at(j) = triangle.at(i).at(j) + d.at(i - 1).at(j);
24                 }
25                 else if (j == int(triangle.at(i).size()) - 1)
26                 {
27                     d.at(i).at(j) = triangle.at(i).at(j) + d.at(i - 1).at(j - 1);
28                 }
29                 else
30                 {
31                     d.at(i).at(j) = triangle.at(i).at(j) + min(d.at(i - 1).at(j - 1), d.at(i - 1).at(j));
32                 }
33             }
34         }
35         int minv = d.at(int(d.size()) - 1).at(0);
36         for (int i = 1; i < int(d.at(int(d.size())-1).size()); i++)
37         {
38             if (d.at(d.size()-1).at(i)<minv)
39             {
40                 minv = d.at(d.size() - 1).at(i);
41             }
42         }
43         return minv;
44     }
45 };
46 
47 int main()
48 {
49     Solution s;
50     vector<vector<int>> tri;
51     int a1[] = { 2 };
52     int a2[] = { 3, 4 };
53     int a3[] = { 6, 5, 7 };
54     int a4[] = { 4, 1, 8, 3 };
55     //tri.push_back(vector<int>(a1,a1+1));
56     //tri[0].push_back(1); tri[0].push_back(9);
57     tri.push_back(vector<int>(a1, a1 + 1));
58     tri.push_back(vector<int>(a2, a2 + 2));
59     tri.push_back(vector<int>(a3, a3 + 3));
60     tri.push_back(vector<int>(a4, a4 + 4));
61     cout<<s.minimumTotal(tri)<<endl;
62     return 0;
63 }

以下为优化后：空间复杂度变为O(1)。

 1 class Solution {
 2 public:
 3     int minimumTotal(vector<vector<int> > &triangle) {
 4         if (triangle.empty())
 5             return 0;
 6         for (int i = triangle.size() - 2; i >= 0; i--)
 7         {
 8             for (int j = 0; j < i + 1; j++)
 9             {
10                 triangle[i][j] += min(triangle[i+1][j],triangle[i+1][j+1]);
11             }
12         }
13         return triangle[0][0];
14     }
15 };