leetcode

commit 16621cc2814b0348681f8d2f53be709aeb0a14f1
parent df2f9c8ec72391b628379c84ea474a1a5168848a
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Wed,  1 Feb 2023 22:23:17 +0100

Algorithm I: Day 12

Diffstat:
A
Problems/0120.cpp
 | 
16
++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 17 insertions(+), 0 deletions(-)
diff --git a/Problems/0120.cpp b/Problems/0120.cpp
@@ -0,0 +1,16 @@
+class Solution {
+public:
+  int minimumTotal(vector<vector<int>> &triangle) {
+    int h = triangle.size();
+
+    for (int i = 0; i < h - 1; i++) {
+      vector<int> vec(i + 2, INT_MAX);
+      for (int j = 0; j <= i; j++) {
+        vec[j] = min(vec[j], triangle[i][j]);
+        vec[j + 1] = min(vec[j + 1], triangle[i][j]);
+      }
+      for (int j = 0; j <= i + 1; j++) triangle[i + 1][j] += vec[j];
+    }
+    return *min_element(triangle.back().begin(), triangle.back().end());
+  }
+};
diff --git a/README.md b/README.md
@@ -86,6 +86,7 @@ for solving problems.
 |  0117  |   Medium   | [Populating Next Right Pointers in Each Node II](Problems/0117.cpp)                              |
 |  0118  |    Easy    | [Pascal's Triangle](Problems/0118.cpp)                                                           |
 |  0119  |    Easy    | [Pascal's Triangle II](Problems/0119.cpp)                                                        |
+|  0120  |   Medium   | [Triangle](Problems/0120.cpp)                                                                    |
 |  0121  |    Easy    | [Best Time to Buy and Sell Stock](Problems/0121.cpp)                                             |
 |  0122  |   Medium   | [Best Time to Buy and Sell Stock II](Problems/0122.cpp)                                          |
 |  0124  |    Hard    | [Binary Tree Maximum Path Sum](Problems/0124.cpp)                                                |