House Robber

• Create a recursive function, say robFrom(index, nums).
• The base case for the recursion is when index is out of bounds of the nums array (i.e., index >= nums.length). In this case, return 0 as no more houses can be robbed.
• In the recursive step, for the current house at index, there are two choices:
  1. Rob the current house: The profit is nums[index] plus the result of a recursive call starting from index + 2 (since the next house cannot be robbed).
  2. Skip the current house: The profit is the result of a recursive call starting from index + 1.
• Return the maximum of these two choices.
• The initial call to the function will be robFrom(0, nums).

This method involves creating a recursive function that, for each house, calculates the maximum profit by considering two scenarios: robbing the current house or skipping it. If we rob the house at index i, we gain nums[i] and must skip the next house, so we recursively call the function for index i + 2. If we skip house i, we can move to the next house, so we recursively call for index i + 1. The function returns the maximum of these two outcomes. This process continues until we've considered all houses.

1class Solution {2    public int rob(int[] nums) {3        return robFrom(0, nums);4    }5 6    private int robFrom(int i, int[] nums) {7        // Base case: If we are past the last house, we can't rob anymore.8        if (i >= nums.length) {9            return 0;10        }11 12        // Option 1: Rob the current house (nums[i]) and skip the next one (i+1).13        int robCurrent = nums[i] + robFrom(i + 2, nums);14 15        // Option 2: Skip the current house and consider the next one (i+1).16        int skipCurrent = robFrom(i + 1, nums);17 18        // Return the maximum of the two options.19        return Math.max(robCurrent, skipCurrent);20    }21}

The main drawback is its performance. The number of recursive calls grows exponentially with the number of houses, as the function repeatedly solves the same subproblems. For an input array of size n, the time complexity is O(2^n).

• Create a memoization array, memo, of the same size as nums, initialized with a value indicating that the state has not been computed (e.g., -1).
• Create a recursive helper function, robFrom(index, nums, memo).
• The base case is the same: if index is out of bounds, return 0.
• Before computing, check if memo[index] has been calculated. If so, return memo[index].
• If not, calculate the result using the same recurrence as the brute-force approach: max(nums[index] + robFrom(index + 2, ...), robFrom(index + 1, ...)).
• Store this result in memo[index] before returning it.
• The initial call will be robFrom(0, nums, memo).

To optimize the brute-force approach, we can store the results of subproblems in a memoization table (an array in this case). This technique is a form of top-down dynamic programming. We create a memo array, where memo[i] will store the maximum amount of money that can be robbed from house i to the end of the street.

Before making the recursive calls to compute the result for index i, we first check if memo[i] has already been computed. If it has, we simply return the stored value. Otherwise, we perform the computation, store the result in memo[i], and then return it. This ensures that each subproblem is solved only once.

1import java.util.Arrays;2 3class Solution {4    private int[] memo;5 6    public int rob(int[] nums) {7        memo = new int[nums.length];8        Arrays.fill(memo, -1); // Initialize memo table with -19        return robFrom(0, nums);10    }11 12    private int robFrom(int i, int[] nums) {13        if (i >= nums.length) {14            return 0;15        }16        // If we have already solved this subproblem, return the stored result.17        if (memo[i] != -1) {18            return memo[i];19        }20 21        // Rob current house + max from house i+2 onwards22        int robCurrent = nums[i] + robFrom(i + 2, nums);23        // Skip current house, get max from house i+1 onwards24        int skipCurrent = robFrom(i + 1, nums);25 26        // Store the result in the memo table and return it.27        memo[i] = Math.max(robCurrent, skipCurrent);28        return memo[i];29    }30}

This optimization drastically reduces the time complexity from exponential to linear, O(n), because each state robFrom(i, ...) is computed at most once. The space complexity is O(n) to store the memoization table and for the recursion call stack.

• Handle edge cases: if nums is empty, return 0; if it has one element, return that element.
• Create a DP array, dp, of the same size as nums.
• Initialize the base cases:
  • dp[0] = nums[0]
  • dp[1] = max(nums[0], nums[1])
• Iterate from i = 2 to nums.length - 1.
• In each iteration, apply the recurrence relation: dp[i] = max(dp[i-1], dp[i-2] + nums[i]).
  • dp[i-1] represents the choice of not robbing house i.
  • dp[i-2] + nums[i] represents the choice of robbing house i.
• The final answer is the last element of the dp array, dp[nums.length - 1].

Instead of a top-down recursive approach, we can solve the problem iteratively in a bottom-up fashion. We define a dp array where dp[i] stores the maximum amount of money that can be robbed from the first i+1 houses (i.e., from house 0 to house i).

The state transition is based on the same decision at each house i:

1. Don't rob house i: The max profit is the same as the max profit up to house i-1, which is dp[i-1].
2. Rob house i: The max profit is nums[i] plus the max profit up to house i-2 (since we can't rob i-1), which is nums[i] + dp[i-2].

So, the recurrence relation is dp[i] = max(dp[i-1], dp[i-2] + nums[i]).

We handle the base cases for the first one or two houses and then iterate through the rest of the array to fill the dp table. The final answer is the value at the last index of the dp array.

1class Solution {2    public int rob(int[] nums) {3        if (nums == null || nums.length == 0) {4            return 0;5        }6        if (nums.length == 1) {7            return nums[0];8        }9 10        int[] dp = new int[nums.length];11        12        // Base cases13        dp[0] = nums[0];14        dp[1] = Math.max(nums[0], nums[1]);15 16        // Fill the rest of the dp table17        for (int i = 2; i < nums.length; i++) {18            // dp[i-1] -> Don't rob house i19            // nums[i] + dp[i-2] -> Rob house i20            dp[i] = Math.max(dp[i-1], nums[i] + dp[i-2]);21        }22 23        return dp[nums.length - 1];24    }25}

This approach has a time complexity of O(n) and a space complexity of O(n) for the DP array. It avoids recursion, thus eliminating the risk of stack overflow and the overhead associated with function calls.

• Initialize two variables, rob1 = 0 and rob2 = 0. rob1 will store the maximum profit ending at the previous house considered, and rob2 will store the maximum profit ending at the house before that.
• Iterate through each amount num in the nums array.
• In each iteration, calculate the maximum profit if we consider the current house num. This would be max(num + rob2, rob1).
  • num + rob2: Rob the current house (num) plus the max profit from two houses ago (rob2).
  • rob1: Don't rob the current house, so the max profit is the same as the max profit from the previous house (rob1).
• Store this new maximum in a temporary variable, say temp.
• Update rob2 to be the old rob1.
• Update rob1 to be temp.
• After iterating through all the houses, rob1 will hold the maximum possible profit. Return rob1.

We can optimize the space complexity of the iterative DP approach. Observing the recurrence relation dp[i] = max(dp[i-1], dp[i-2] + nums[i]), we see that to compute the maximum profit for the current house, we only need the results from the previous two houses. This means we don't need to maintain the entire dp array.

We can use two variables to track the required information. Let's use rob1 to store the maximum profit up to the previous house (dp[i-1]) and rob2 to store the maximum profit up to the house before that (dp[i-2]).

As we iterate through the houses, we calculate the current maximum profit, current_max = max(rob1, rob2 + nums[i]). Then, for the next iteration, the previous rob1 becomes the new rob2, and current_max becomes the new rob1.

1class Solution {2    public int rob(int[] nums) {3        if (nums == null || nums.length == 0) {4            return 0;5        }6 7        int rob1 = 0; // Represents the max profit ending at the previous house (dp[i-1])8        int rob2 = 0; // Represents the max profit ending at the house before previous (dp[i-2])9 10        // [rob2, rob1, num, num+1, ...]11        for (int num : nums) {12            // The new max profit is either robbing the current house (num + rob2)13            // or not robbing it (rob1).14            int temp = Math.max(num + rob2, rob1);15            16            // Update pointers for the next iteration17            rob2 = rob1;18            rob1 = temp;19        }20 21        return rob1;22    }23}

This optimized solution maintains the O(n) time complexity but reduces the space complexity to O(1), making it the most efficient approach.