Fastrail08

House Robber 2 (Leetcode 198) Space Unoptimised Version

Jul 19th, 2025
863
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.34 KB | None | 0 0
  1. class Solution {
  2. public:
  3.     //SPACE IS UNOPTIMISED HERE, AS WE DO BLIND RECURSION AND KEEP TRACK OF WHAT WAS THE LAST HOUSE WE ROBBED. So we need to memoise the lastHouseRobbedIndex which increases the space by a factor of O(n) making the space O(N^2). But THIS SOLUTION IS AN ACCEPTED SOLUTION, with T.C. as O(N^2) only though it will be slow because of extra space declaration and managing it throughout recursion.
  4.     int getMaxMoney(int level, int lastHouseRobbedIndex, int zeroPicked, vector<int> &nums, vector<vector<vector<int> > >&memo){
  5.         int n = nums.size();
  6.         // all houses processed in path.
  7.         if(level >= nums.size()){
  8.             return 0;
  9.         }
  10.         if(lastHouseRobbedIndex != -1 && memo[level][lastHouseRobbedIndex][zeroPicked] != -1){
  11.             return memo[level][lastHouseRobbedIndex][zeroPicked];
  12.         }
  13.         int rob = 0, notRob = 0;
  14.         //levels = each house
  15.         //options = rob or not
  16.  
  17.         //rob ONLY IF THE LAST HOUSE WAS NOT ROBBED OR THIS IS THE FIRST HOUSE(as there is no last house which could be robbed)
  18.         if(lastHouseRobbedIndex == -1 || level - lastHouseRobbedIndex > 1){
  19.             //As the array is circular, make sure the first and last house are never robbed together
  20.             //If the first house is robbed, don't rob the last to avoid breaking property of adjacency
  21.             //If on level (n - 1), don't include if 0th house was robbed
  22.             if(level != n - 1 || !zeroPicked){
  23.                 rob = nums[level] + getMaxMoney(level + 1, level, level == 0 ? 1 : zeroPicked, nums, memo);
  24.             }
  25.         }
  26.  
  27.         //don't rob - not robbing the house on level makes no impact on the answer being formed as the property that can be violated is only when you rob a house (ADJACENT ROBBERIES), not robbing do not impact property
  28.         notRob = getMaxMoney(level + 1, lastHouseRobbedIndex, zeroPicked, nums, memo);
  29.         if(lastHouseRobbedIndex != -1){
  30.             memo[level][lastHouseRobbedIndex][zeroPicked] = max(rob, notRob);
  31.         }
  32.         return max(rob, notRob);
  33.     }
  34.     int rob(vector<int>& nums) {
  35.         int n = nums.size();
  36.         //memo key = memo(level, lastHouse) = memo(n, n);
  37.         vector<vector<vector<int> > > memo(n, vector<vector<int> >(n, vector<int>(2, -1)));
  38.         return getMaxMoney(0, -1, 0, nums, memo);
  39.     }
  40. };
Advertisement
Add Comment
Please, Sign In to add comment