198. House Robber

#dp

Problem

House Robber - LeetCodeLeetCode

Intuition

We need to know the subsequences. As we are iterating from left to right and we need to pick non-adjacent houses.

https://medium.com/@kaido0121/leetcode-patterns-dynamic-programming-1b65610ce22d

We are generating all possible subsequences with the given constraint and maintaining max possible money we can rob. A subsequence need not be only one step away, it can be "n" steps away.

Time Complexity

Space Complexity

Solution

class Solution {
    public int rob(int[] nums) {
        // return recursiveHelper(nums.length-1, nums);
        // int[] dp = new int[nums.length];
        // Arrays.fill(dp, -1);

        // return memoizationHelper(nums.length-1, nums, dp);
        // return tabulationHelper(nums);
        return tabulationSpaceOptimizedHelper(nums);
    }

    // Dynamic Programming - Tabulation (Space-Optimized)
    private int tabulationSpaceOptimizedHelper(int[] nums) {
        // n -> Number of houses/ nums.length
        // Time Complexity: O(n)
        // Space Complexity: O(1), no extra space is used

        int n = nums.length;
        int prev2 = 0; // Max value till i-2
        int prev1 = nums[0]; // Max value till i-1

        for(int i=1; i<n; i++) {
            int f1 = nums[i] + prev2; // Max value if we rob the current house
            int f2 = prev1; // Max value if we don't rob the current house
            int current = Math.max(f1, f2); // Max value till the current house
            prev2 = prev1;
            prev1 = current;
        }

        return prev1; // Return the max value till the last house
    }

    // Dynamic Programming - Tabulation
    private int tabulationHelper(int[] nums) {
        // n -> Number of houses/ nums.length
        // Time Complexity: O(n)
        // Space Complexity: O(n), "dp" array is used

        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0]; // Base case: Max value till the first house is the value of the first house

        for(int i=1; i<n; i++) {
            int f1 = nums[i]; // Max value if we rob the current house
            if(i > 1) { // To make sure we are not stepping into negative indices
               f1 += dp[i-2]; /
            }
            int f2 = dp[i-1]; // Max value if we don't rob the current house
            dp[i] = Math.max(f1, f2); // Max value till the current house
        }

        return dp[n-1]; // Return the max value till the last house
    }

    // Dynamic Programming - Memoization
    private int memoizationHelper(int index, int[] nums, int[] dp) {
        // n -> Number of houses/ nums.length
        // Time Complexity: O(n)
        // Space Complexity: O(n), "dp" array is used

        // Base case: Max value till the first house is the value of the first house
        if(index == 0) {
            return nums[0]; 
        }

        // Base case: No more houses to rob
        if(index < 0) {
            return 0; 
        }

        if(dp[index] != -1) {
            return dp[index]; // Return the precalculated max value if already computed
        }

        // Max value if we rob the current house
        int f1 = nums[index] + memoizationHelper(index-2, nums, dp); 
        // Max value if we don't rob the current house
        int f2 = memoizationHelper(index-1, nums, dp); 
        
        // Store the computed max value in the DP table and return it
        return dp[index] = Math.max(f1, f2); 
    }

    // Recursive Approach
    private int recursiveHelper(int index, int[] nums) {
        // n -> Number of houses/ nums.length
        // Time Complexity: O(2^n), to generate all the possible subsequences
        // Space Complexity: O(n) + O(h), "dp" array is used, "h" is recursion stack

        // Base case: Max value till the first house is the value of the first house
        if(index == 0) {
            return nums[0]; 
        }

        // Base case: No more houses to rob
        if(index < 0) {
            return 0; 
        }

        // Max value if we rob the current house
        int f1 = nums[index] + recursiveHelper(index-2, nums);
        // Max value if we don't rob the current house
        int f2 = recursiveHelper(index-1, nums); 

        return Math.max(f1, f2); // Return the maximum of the two possibilities
    }
}