House Robber

Thought Process

The House Robber problem requires finding the maximum amount of money that can be robbed from houses arranged in a line, with the constraint that adjacent houses cannot be robbed. Here are two approaches:

Approach 1: Memoization (Top-Down) - Use recursion with memoization to store subproblem results. If there is only one house, return its value. If there are two houses, return the maximum of the two. For more than two houses, recursively compute the maximum of either robbing the current house and skipping the previous one or skipping the current house.

Approach 2: Tabulation (Bottom-Up) - Use an iterative approach to build the solution from the base cases upwards. Initialize an array ('t') to store the maximum amount that can be robbed up to each house. For each house, compute the maximum amount as the maximum of either robbing the current house + the amount from two houses back or skipping the current house and taking the amount from the previous house i.e. calculate maximum of (nums[i] + t[i-2]) or t[i-1] .

Approach 1: Memoization (Top-Down)

class Solution {
public:

    int t[105]; // As maximum input size is 100
    int maxSum(vector<int> &nums, int sz){

        // Base case
        if(sz==1)
            return nums[0];

        if(sz==2)
            return max(nums[0],nums[1]);

        else{
            if(t[sz] != -1)
                return t[sz];

            return t[sz] = max(maxSum(nums,sz-1),nums[sz-1]+maxSum(nums,sz-2));
        }
    }
    int rob(vector<int>& nums) {
        
        int sz = nums.size();
        memset(t,-1,sizeof(t)); // Initialize the DP array to -1.
        return maxSum(nums,sz);
    }
};

Approach 2: Tabulation (Bottom-Up)

class Solution {
public:
    int rob(vector<int>& nums) {
        
        int t[105]; // As maximum input size is 100
        int sz = nums.size();

        // Base case
        if(sz==1)
            return nums[0];
        
        // Following 1-based indexing.
        t[1] = nums[0]; // Case when only one element is present.
        t[2] = max(nums[0],nums[1]); // Case when two elements are present.

        for(int i=3;i<=sz;i++){
            t[i] = max(t[i-1],nums[i-1]+t[i-2]); // Maximum of (reject,select)
        }
        return t[sz];
    }
};

Code Complexity

Time Complexity: O(n)

Both approaches iterate through the array once, ensuring linear time complexity.

Space Complexity: O(n)

Both approaches use an array of size 'n' to store intermediate results.