codecakes · August 6, 2024 20:26 · Aug 6, 2024
diff --git a/minimum_output_triangle.py b/minimum_output_triangle.py
@@ -0,0 +1,38 @@
+
+# top-down: Larger Number TLE
+class Solution:
+    def minimumTotal(self, triangle: List[List[int]]) -> int:
+        if len(triangle) == 1:
+            return triangle[0][0]
+        res = tuple()
+        level = 0
+        curr_list = triangle[level]
+        next_level = level + 1
+        next_list = triangle[next_level]
+        for idx in range(next_level):
+            for offset, each_num in enumerate(next_list[idx:idx+2]):
+                res += (self.doMinTotal(each_num + curr_list[idx], offset+idx, next_level, triangle),)
+        return min(res)
+
+    def doMinTotal(self, ans: int, start_idx: int, level: int, triangle: List[List[int]]) -> int:
+        next_level = level + 1
+        if next_level == len(triangle):
+            return ans
+        res = tuple()
+        next_list = triangle[next_level]
+        for offset, each_num in enumerate(next_list[start_idx:start_idx+2]):
+            res += (self.doMinTotal(ans + each_num, start_idx + offset, next_level, triangle),)
+        return min(res)
+
+
+# Bottom-up, Efficient
+class Solution:
+    def minimumTotal(self, triangle: List[List[int]]) -> int:
+        if len(triangle) == 1:
+            return triangle[0][0]
+        for level in range(len(triangle) - 1, 0, -1):
+            curr_list = triangle[level]
+            prev_list: List[int] = triangle[level-1]
+            for idx in range(level):
+                triangle[level-1][idx] += min(curr_list[idx: idx+2])
+        return triangle[0][0]