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 {

    int[] t = new int[1001];
    public int mxSum(int[] nums, int sz){

        if(sz==1)
            return nums[0];
        
        if(sz==2)
            return Math.max(nums[0],nums[1]);
        else{
            if(t[sz]!=-1)
                return t[sz];
            else 
                return t[sz] = Math.max(mxSum(nums,sz-1),nums[sz-1]+mxSum(nums,sz-2));
        }
    }
    public int rob(int[] nums) {

        int sz = nums.length;
        Arrays.fill(t,-1);
        int ans = mxSum(nums,sz);
        return ans;
    }
}

Approach 2: Tabulation (Bottom-Up)

class Solution {
    public int rob(int[] nums) {
        
        int sz = nums.length;
        int[] t = new int[sz+1];

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

        // t[i] denotes maximum amount of money that can be robbed given we have i houses
        t[1] = nums[0];
        t[2] = Math.max(nums[0],nums[1]);

        for(int i=3;i<=sz;i++){

            t[i] = Math.max(t[i-1],nums[i-1]+t[i-2]);
        }
        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.