hi, let Avik connect you.


** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.

** You can check all the posts on the Posts page.

** More about me in the About Me section.

House Robber


  • Approach:

    1. Started from the 0th position house.

    2. As mentioned, if we add the cost of the current house skipped the cost of robbing the next house.

    3. Else take if we do not add the cost of the current house, added the cost of robbing the next house.

    4. For each ith index, tried steps 2 and 3, and calculated the max between them.

    5. As there will overlapping subproblems to solve we used a memoization array to store the values calculated earlier.

    6. In case of repetitive sub-problems returned those values.


  • Time and Space Complexity:

      • Time Complexity: O(n) + Auxilary Stack.

      • Space Complexity: O(n)


Code [C++]

class Solution {

public:


int solve(vector<int>&nums, int pos, vector<int>&dp, int n){

if(pos >= n) return 0;

if(dp[pos] != -1) return dp[pos];

int maxValue = 0;

maxValue = max(maxValue, solve(nums, pos + 2, dp, n) + nums[pos]);

maxValue = max(maxValue, solve(nums, pos + 1, dp, n));

return (dp[pos] = maxValue);

}


int rob(vector<int>& nums) {

int n = size(nums);

if(n == 1) return nums[0];

vector<int>dp(n, -1);

int ans = solve(nums, 0, dp, n);

return ans;

}

};