Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- public:
- //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.
- int getMaxMoney(int level, int lastHouseRobbedIndex, int zeroPicked, vector<int> &nums, vector<vector<vector<int> > >&memo){
- int n = nums.size();
- // all houses processed in path.
- if(level >= nums.size()){
- return 0;
- }
- if(lastHouseRobbedIndex != -1 && memo[level][lastHouseRobbedIndex][zeroPicked] != -1){
- return memo[level][lastHouseRobbedIndex][zeroPicked];
- }
- int rob = 0, notRob = 0;
- //levels = each house
- //options = rob or not
- //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)
- if(lastHouseRobbedIndex == -1 || level - lastHouseRobbedIndex > 1){
- //As the array is circular, make sure the first and last house are never robbed together
- //If the first house is robbed, don't rob the last to avoid breaking property of adjacency
- //If on level (n - 1), don't include if 0th house was robbed
- if(level != n - 1 || !zeroPicked){
- rob = nums[level] + getMaxMoney(level + 1, level, level == 0 ? 1 : zeroPicked, nums, memo);
- }
- }
- //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
- notRob = getMaxMoney(level + 1, lastHouseRobbedIndex, zeroPicked, nums, memo);
- if(lastHouseRobbedIndex != -1){
- memo[level][lastHouseRobbedIndex][zeroPicked] = max(rob, notRob);
- }
- return max(rob, notRob);
- }
- int rob(vector<int>& nums) {
- int n = nums.size();
- //memo key = memo(level, lastHouse) = memo(n, n);
- vector<vector<vector<int> > > memo(n, vector<vector<int> >(n, vector<int>(2, -1)));
- return getMaxMoney(0, -1, 0, nums, memo);
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment