leetcode

commit c23e5e8c6718f0be24e9a4a0ab458014ddcd600e
parent 710523a934fae5f7c09aa93147081be4bad87c7a
Author: AndrewLockVI <andrewlaack1@gmail.com>
Date:   Mon, 15 May 2023 12:32:30 -0500

Completed triangle problem using dart

Diffstat:
A
triangle/triangle.dart
 | 
31
+++++++++++++++++++++++++++++++

1 file changed, 31 insertions(+), 0 deletions(-)
diff --git a/triangle/triangle.dart b/triangle/triangle.dart
@@ -0,0 +1,31 @@
+//Given a matrix of i + 1 size where i is the index of the list (0 index)
+//return the minimum path from the top to the bottom where you can only either
+//go to i or i+1 on the row below the current row.
+//The time complexity of this code is O(n^2)
+//Time: TLE
+//Memory: TLE
+class Solution {
+  List<List<int>> triangle = [];
+  int minimumTotal(List<List<int>> tri) {
+      triangle = tri;
+      return min( 0, 0, {});
+  }
+
+  int min(int current_index , int row, Map<String,int> memo){
+      if(memo.containsKey(current_index.toString() + " " + row.toString())){
+          int current_val = (memo[current_index.toString() + " " + row.toString()] ?? 0);
+          return current_val;
+      }
+      if(row == triangle.length){
+          return 0;
+      }
+      int curr = min( current_index , row + 1 , memo);
+      int right = min( current_index + 1 , row + 1, memo);
+      if(curr < right){
+          return curr + triangle[row][current_index];
+      }
+      int lowest_for_index = right + triangle[row][current_index];
+      memo[current_index.toString() + " " + row.toString()] = lowest_for_index;
+      return lowest_for_index;
+  }
+}