leetcode

commit f3e8505bbb4f6edff87bc49bbd28cb65b72ebd8e
parent bf26d1d1f9affb64504143114df5b02b56393437
Author: AndrewLockVI <andrewlaack1@gmail.com>
Date:   Wed, 31 May 2023 12:50:54 -0500

Completed unique binary search trees using memoization, dp, and recursion

Diffstat:
A
unique-binary-search-trees/unique-binary-search-treesV2.dart
 | 
32
++++++++++++++++++++++++++++++++

1 file changed, 32 insertions(+), 0 deletions(-)
diff --git a/unique-binary-search-trees/unique-binary-search-treesV2.dart b/unique-binary-search-trees/unique-binary-search-treesV2.dart
@@ -0,0 +1,32 @@
+//Added memoization which stops me from getting a tle.
+//Time: 290ms Beats: 100%
+//Memory: 140.1MB Beats: 100%
+
+class Solution {
+  int numTrees(int n) {
+    List<int> val_list = [];
+    for(int i = 1 ; i <= n ; ++i){
+        val_list.add(i);
+    }
+    return trees(val_list, {});
+  }
+
+int trees(List<int> vals, Map<int, int> memo){
+  if(memo.containsKey(vals.length)){
+    return (memo[vals.length] ?? 0);
+  }
+  if(vals.length == 0){
+    return 1;
+  }
+
+  int current_val = 0;
+  for(int i = 0 ; i < vals.length ; ++i){
+    List<int> left = vals.sublist(0,i);
+    List<int> right = vals.sublist(i + 1);
+    current_val += trees(left, memo) * trees(right,memo);
+  }
+  memo[vals.length] = current_val;
+  return current_val;
+}
+
+}