House Robber 2 (Leetcode 198) SPACE OPTIMIZED VERSION(VERY IMPORTANT)

//HERE T.C. IS O(N^2) and space is O(N) which makes it best solution for JUMP DP variations.
/*
HAHHAHAHHAHHAHHHAHAHHAH
I was able to solve it with a new code, which runs in T.C. O(N^2) but space is OPTIMISED to O(N). It beats 100% of the users in run time and ran in 0ms. I think this happened because of 3 reasons:
1) Large impact because it causes more sub problems to overlap and hence less recursive calls
2) Large Impact because it helps us skip invalid states unlike blind recursion, this is indeed smart recursion
3)Small impact because the size of memo table reduced, so easier to manage through recursive state
*/
class Solution {
public:

        //CALL ONLY TO ALL THE VALID LEVELS FROM CURRENT LEVEL
        //VALID IS where you will have all the options available/they are all valid without needing to use a CONDITIONAL to check if the options are valid or not at the current level
        //when both the options are valid and available, we choose the option that is the BEST among them, as in this question, why would you NOT ROB a bank, when you CAN ROB the bank WITHOUT any hesitation and still avoid VIOLATING the property(ADJACENCY) stated in the question.
        //WHAT IS DIFFERENT??
        /*
        ***********VERY VERY IMPORTANT:
        Previously we FORM ALL the possible VALID combinations to rob and keeping in mind to not violate the property of adjacency and then choose the best combination, but we were doing blind recursion, doing (level + 1) at every level after exploring ALL the valid options at that level with the help of a CONDITIONAL (conditional tells you when to explore a particular option to avoid generating any INVALID sequences/ OR sequences/subsets/subsequences that violates the property) and a CONDITIONAL requires something to be TRACKED while performing recursion, so that CONDITIONAL is always updated and in sync with the subset/subsequences being formed.
such as, if we are at level, we update lastHouseRobbedIdx = 1, when we rob a house, but if we don't rob, then we simply make lastHouseRobbedIdx = 0 before moving to the next level(level + 1), telling that we didn't rob the last house at the next level(level + 1), which helps us make decision at level + 1, if we can explore the option rob at this level.

BUT NOW we don't need to USE A CONDITIONAL TO CHECK WHETHER SOME OPTION IS VALID OR NOT AT SOME LEVEL, because instead of using conditional and only explore VALID options, we SIMPLY MOVE from a LEVEL, TO ALL THE POSSIBLE LEVELS called as VALID levels, WHERE ALL THE OPTIONS ARE VALID, here rob or not rob. AND as all the options are valid, we simply explore that SINGULAR OPTION that helps us make the BEST ANSWER. HERE ROBBING A BANK gives me money, and NOT ROBBING, gives me nothing. SO WE ROB at every VALID levels, without hesitation, because we ONLY EXPLORE VALID LEVELS, so robbing can be explored in any of these. ROBBING BEING THE BEST OPTION(maximises the answer), we ONLY ROB. THERE IS NO NEED TO EXPLICITLY call the 'DON'T ROB' option because it is not optimal.

JUST ASK YOURSELF, IF THERE WAS NO PROPERTY ON ADJACENCY, we would have ROBBED at EVERY LEVEL/EVERY HOUSE.
SO IS THIS, ONCE WE ROB A HOUSE AT A LEVEL, we MOVE TO THE NEXT LEVEL DIRECTLY WHERE ROBBING IS POSSIBLE AGAIN, SKIPPING ALL THE OPTIONS IN BETWEEN WHERE WE CAN'T ROB. SO WHY WON'T YOU ROB. AND WE EXPLORE ALL THE VALID LEVELS FROM A LEVEL, WHERE ROBBING IS POSSIBLE AGAIN, WITH THE HELP OF A LOOP(in subsequence type question, where order can't be changed) OR BINARY SEARCH (to move to the nearest/JUST next VALID LEVEL, in subset, where order can be changed with the help of SORTING). AS WE ARE FORMING ALL THE POSSIBLE combinations EXCLUDING the combinations which have INVALID LEVELS in them(it is just that we EXPLORE all the COMBINATIONS FORMED BY VALID LEVELS).

*****BASICALLY THE LEVELS EXPLORED ARE THE LEVELS WHERE THE ADJACENCY CONDITION DOES NOT EXIST. SO WE ONLY CHOOSE THE BEST OPTION AT EVERY LEVEL and STILL NOT VIOLATE THE PROPERTY. (ADJACENCY CONDITION DOES NOT FAIL while doing this, because WE ONLY MOVE TO A LEVEL that is VALID, where CHOOSING THE BEST OPTION ONLY(robbing) DOES NOT VIOLATE THE PROPERTY).
ONLY MOVING TO VALID LEVELS HAPPENS WITH THE HELP OF A LOOP OR BINARY SEARCH, WHERE WE PRE CHECK THAT IS IT A VALID LEVEL TO MOVE TO, RELATIVE TO THE CURRENT LEVEL(important), if it is THEN ONLY MOVE TO THAT LEVEL.
RELATIVE TO CURRENT LEVEL IS:
1) HOUSE ROBBER: if current level is robbed, valid levels are in range[level + 2, n - 1], invalid is {level + 1}, as robbing at (level + 1) will violate property of adjacency.
2) HOUSE ROBBER 2: if current level is robbed,
for current level in range[1, n - 1], VALID LEVELS are in range[level + 2, n - 1], INVALID LEVEL {level + 1}
for current level = 0, VALID LEVELS are in range[level + 2, n - 2], INVALID LEVELS {level + 1(1), n - 1}
where [] means an INCLUSIVE RANGE(boundaries included) and {} means a set of elements.
IMPORTANT: RELATIVE TO level = 0, (level + 1)/1 is an invalid level to explore to as it VIOLATES ADJACENCY PROPERTY, AND (n - 1) is an INVALID LEVEL to explore to, because the ARRAY IS CIRCULAR, and because of that house 0 and house (n - 1) are neighbours/adjacent. So if the current level = 0, we run a loop from [level + 2, n - 2] to avoid exploring the invalids.

WE MOVE TO THE LEVELS, WHERE ROBBING IS POSSIBLE NO MATTER WHAT CHOICES WE MAKE/OPTIONS WE EXPLORE, PROPERTY NEVER GETS VIOLATED, SO WE ONLY EXPLORE THE BEST OPTIONS OUT OF ALL OPTIONS as WE ARE FREE TO MAKE EVERY CHOICE.SO WHY CHOOSE A SUBOPTIMAL CHOICE, ONLY CHOOSE BEST
        */

        /*
        ******* IMPORTANT
        In this question we need to have a separate variable zeroPicked that needs to be tracked in recursion
        For question like this, if done by this method, we don't have the memory of what was picked before in some previous level IMPLICITLY, and we are not actively tracking lastIdx EXPLICITLY. We move to ALL the next VALID levels RELATIVE to what was VALID ACCORDING TO THE LAST LEVEL.

        For cases like these where [200,3,140,20,10], imagine if 200 was picked, then the valid levels would be
        {140, 20}. So we can move to any of these levels as they are all valids with the help of the LOOP. Suppose we are currently exploring to 140. At 140, we pick it, making the sum = 340. The valid levels RELATIVE to 140 are {10}. So we explore 10, move to 10, pick 10,making sum = 350. THIS IS WROOOOOOONNNGGGGGG.
        As 10 is valid RELATIVE TO 140, but as we don't have the memory of what all elements have been included already, we can't check what all elements were also included prior to 140. In this case we picked 200 also before 140, which makes 10 INVALID RELATIVE to 200 as they are neighbours in circular array. But on the level of 140, we can't remember if 0th house(200) was included or not. So we EXPLICITLY NEED TO TRACK if 0th element was included or not, hence the variable zeroPicked.
        BUT as it is about inclusion/exclusion of a single element, it has only 2 states {0 or 1} / {included or not}.
        AS the PARAMETER zeroPicked is CHANGING throughout recursion,
        INFLUENCING (either decision making in base case OR helping write conditional/transition logic) here it helps us write CONDITIONAL
        NOT DERIVABLE from any other parameters

        THUS zeroPicked should be a part of memo key, just like level.
        */
    int getMaxMoney(int level, int zeroPicked, vector<int> &nums, vector<vector<int> > &memo){
        //base case
        if(level >= nums.size()){
            return 0;
        }
        if(memo[level][zeroPicked] != -1){
            return memo[level][zeroPicked];
        }
        int n = nums.size();
        //levels = house
        //options = ROB (we will always ROB at EACH LEVEL WE GO TO, because ROBBING IS ALWAYS VALID AT EVERY LEVEL(just because we only go to valid levels/ A level where all options are valid to explore to)AND THE BEST OPTION IS TO ROB AT EVERY HOUSE, IF IT IS POSSIBLE.

        int maxMoney = 0;
        //Very Important tracks if the loop at the current level ran or not
        bool flag = false;
        //level + 1 is invalid because of the property of adjacency.
        int nextValidLevelsStart = level + 2;

        //if level = 0, valid levels are upto and including (n - 2). (n - 1) is invalid level as the array is circular, and 0th and (n - 1)th element are adjacent.
        //For level != 0,  valid levels are upto and including(n - 1)
        int nextValidLevelsEnd = level == 0 ? n - 2 : n - 1;

        //******IMPORTANT OBSERVATION(specific to this question only)/ GOOD ONE/ I OBSERVED IT MYSELF haha
        //if 0th house picked/robbed, (n - 1)th house cannot be picked/robbed
        //so update the nextValidLevelsEnd for all levels, where level != 0
        //Now in all the paths where 0th house was robbed, for levels other than 0, there valid range cannot include the last house (n - 1) as the array is circular.
        if(zeroPicked){
            nextValidLevelsEnd = n - 2;
        }

        //Move to all the valid levels with the help of LOOP. Binary Search can't be used, as array can't be sorted, as ORDER here has meaning just like in LIS.
        for(int i = nextValidLevelsStart; i <= nextValidLevelsEnd; i++){
            flag = true;
            //We ONLY EXPLORE THE OPTION TO ROB at every level,as we ARE ALWAYS ON A VALID LEVEL, and Robbing is best option to explore out all the the other option.
            maxMoney = max(maxMoney, nums[level] + getMaxMoney(i, level == 0 ? 1 : zeroPicked, nums, memo));
        }
        //********VERY IMPORTANT IMPLEMENTATION PRACTICE for DP WITH JUMPS VARIATION
        //if flag true, loop ran atleast once, and the money at house[level] was correctly included in the maxmoney
        //but if flag false, loop didn't even run once, and the money at house[level] was not included in the maxMoney (as this happens after we return from the recursive call INSIDE THE LOOP). But the house[level] is a VALID LEVEL, that's why we were able to reach this level and hence we have to INCLUDE the money of house[level] in the maxMoney, as we ALWAYS ROB A VALID LEVEL. The LOOP (not only helps make recursive call to ALL valid levels but it also HELPS to CORRECTLY INCLUDE THE money of the CURRENT LEVEL), IT DIDN'T RUN EVEN ONCE, and because of that, we have to EXPLICITLY ADD THE MONEY of house[level] to maxMoney.
        //So make it a general implementation practice in JUMP DPs, to track a flag inside a LEVEL to check whether the loop ran or not. If not ran/flag = false, EXPLICITLY ADD THE VALUE OF CURRENT LEVEL TO VARIABLES BEING RETURNED FROM LEVEL (here maxMoney);
        //******IMPORTANT
        // As loop didn't run once, meaning there are no valid levels to call from the current level
        // But the current level is a valid level and it's value must be returned.
        //Just because house[level] is VALID and can be robbed but no further houses exist that can be robbed.
        //maxMoney we can make here at this level will be nums[level] + recurse(level + 2, n - 1)
        //But no loop ran/no valid levels further to recurse, maxMoney = nums[level]
        // As the loop didn't run, no point of maxMoney, and it will be 0 for sure, because loop didn't run.
        //****IMPORTANT So the condition could have also looked like return flag == true ? maxMoney : nums[level];
        return memo[level][zeroPicked] = flag == true ? maxMoney : maxMoney + nums[level];
    }

    int rob(vector<int>& nums) {
        int maxMoney = 0;
        //memo key = memo(level, zeroPicked) => memo(n, 2) => 2*n = O(n) space
        vector<vector<int> > memo(nums.size(), vector<int>(2, -1));
        for(int i = 0; i < nums.size(); i++){
            //As the FIRST HOUSE in the subsequence(FIRST in the subsequence of ROBBED HOUSES, not the FIRST in the ORIGINAL NUMS ARRAY) is ALWAYS A VALID LEVEL(no previous houses, no property violation possible)
            //ALWAYS ROB AT THE FIRST HOUSE IN THE SUBSEQUENCE, JUST LIKE AS WE WILL ROB AT EVERY HOUSE IN THE SUBSEQUENCE, BECAUSE OUR SUBSEQUENCE IS FORMED ONLY OF VALID LEVELS.FIRST HOUSE and so as the other houses reached during recursion, are all valid, recursion treats it as VALID, as recursion was able to reach that level, and we can only reach levels that are valid, otherwise we won't have reached that level.
            //USING LOOP GUARANTEES THAT WE GIVE EVERY HOUSE THE CHANCE TO BE ROBBED FIRST IN THE SUBSEQUENCE.
            //IF WE START FROM HOUSE 0, instead of LOOPING, as we do in general INDEX BASED RECURSION, will generate answers/subsequences of houses robbed, where HOUSE 0 is always a part of subsequence/HOUSE 0 will always be ROBBED(as we call recursion on level 0, and it will be treated as a valid level and we always rob on a valid level). AND THIS IS NOT CORRECT. OPTIMAL ANSWER to the problem might or might not include HOUSE 0. SO GIVE EVERY HOUSE THE CHANCE TO BE THE FIRST in THE SUBSEQUENCE.
            maxMoney = max(maxMoney, getMaxMoney(i, 0, nums, memo));
        }
        return maxMoney;
    }
};