house-robberV2.dart (1671B)
1 //The problem with my TLE solution is that I was creating a new memoization table for each different starting point thus 2 //forgetting a lot of the sub problems. Now with my current implementation this is no longer an issue. 3 //Time: 244ms Beats: 85% 4 //Memory: 141.4MB Beats: 92.50% 5 class Solution { 6 Map<String, int> memo = {}; 7 int rob(List<int> nums) { 8 int max = 0; 9 for(int i = 0 ; i < nums.length ; ++i){ 10 int current = maxRobbed(nums, i, {}); 11 if(current > max){ 12 max = current; 13 } 14 } 15 return max; 16 } 17 int maxRobbed(List<int> nums, int current_house , Set<int> no_rob_list){ 18 if(no_rob_list.contains(current_house)){ 19 return 0; 20 } 21 no_rob_list.add(current_house - 1); 22 no_rob_list.add(current_house); 23 no_rob_list.add(current_house + 1); 24 25 if(nums.length == 0){ 26 return 0; 27 } 28 if(nums.length == 1){ 29 return nums[0]; 30 } 31 String curr = ""; 32 List<int> no_vals = []; 33 for (int number in nums) { 34 no_vals.add(number); 35 } 36 no_vals.sort(); 37 for(int vals in no_vals){ 38 curr += vals.toString() + " "; 39 } 40 curr += current_house.toString(); 41 if(memo[curr] != null){ 42 int ret_int = (memo[curr] ?? 0); 43 return ret_int; 44 } 45 46 int current_val = nums[current_house]; 47 int max = 0; 48 for(int i = 0 ; i < nums.length ; ++i){ 49 int current = maxRobbed(nums, i, Set.from(no_rob_list)); 50 if(current > max){ 51 max = current; 52 } 53 } 54 memo[curr] = max + current_val; 55 return max + current_val; 56 } 57 }