leetcode

commit 04e132e73681056177e65b874f13480d8bf81b16
parent fba7a58cff9a28a2c3e3196e6d63b987c5456c0e
Author: AndrewLockVI <andrewlaack1@gmail.com>
Date:   Thu, 18 May 2023 13:09:56 -0500

Completed house robber using DP, dart, and recursion

Diffstat:
A
house-robber/house-robberV2.dart
 | 
57
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++

1 file changed, 57 insertions(+), 0 deletions(-)
diff --git a/house-robber/house-robberV2.dart b/house-robber/house-robberV2.dart
@@ -0,0 +1,57 @@
+//The problem with my TLE solution is that I was creating a new memoization table for each different starting point thus 
+//forgetting a lot of the sub problems. Now with my current implementation this is no longer an issue.
+//Time: 244ms Beats: 85%
+//Memory: 141.4MB Beats: 92.50%
+class Solution {
+  Map<String, int> memo = {};
+  int rob(List<int> nums) {
+      int max = 0;
+      for(int i = 0 ; i < nums.length ; ++i){
+          int current = maxRobbed(nums, i, {});
+          if(current > max){
+              max = current;
+          }
+      }
+      return max;
+  }
+  int maxRobbed(List<int> nums, int current_house , Set<int> no_rob_list){
+      if(no_rob_list.contains(current_house)){
+          return 0;
+      }
+      no_rob_list.add(current_house - 1);
+      no_rob_list.add(current_house);
+      no_rob_list.add(current_house + 1);
+
+      if(nums.length == 0){
+          return 0;
+      }
+      if(nums.length == 1){
+          return nums[0];
+      }
+      String curr = "";
+      List<int> no_vals = [];
+      for (int number in nums) {
+          no_vals.add(number);
+      } 
+      no_vals.sort();
+      for(int vals in no_vals){
+          curr += vals.toString() + " ";
+      }
+      curr += current_house.toString();
+      if(memo[curr] != null){
+          int ret_int =  (memo[curr] ?? 0);
+          return ret_int;
+      }
+
+      int current_val = nums[current_house];
+      int max = 0;
+      for(int i = 0 ; i < nums.length ; ++i){
+          int current = maxRobbed(nums, i, Set.from(no_rob_list));
+          if(current > max){
+              max = current;
+          }
+      }
+      memo[curr] = max + current_val;
+      return max + current_val;
+  }
+}