House Robber Problem

Given a list of houses, each containing some money, you need to determine the maximum amount of money you can rob without robbing two consecutive houses.

For example, if the houses have the following money: [2, 7, 9, 3, 1], the maximum money you can rob is 12 by robbing the first, third, and fifth houses.

Approach to the Solution
To solve this problem, we can break down the solution into a series of increasingly optimized approaches:

• Recursive Solution
• Memoization Solution
• Tabulation Solution
• Space-Optimized Tabulation Solution

1. Recursive Solution
The recursive approach is the most straightforward but inefficient. The idea is to try robbing each house and recursively check for the best outcome. For each house, you have two options: rob it or skip it.

If you rob the current house, you cannot rob the next one, so you move to the house after the next.
If you skip the current house, you move to the next house.
The recursive function explores all possible combinations and returns the maximum possible profit.

int solveUsingRecursion(const vector<int> &houses, int currentIndex) {
  if (currentIndex >= houses.size()) {
    return 0;
  }

  int robCurrent = houses[currentIndex] + solveUsingRecursion(houses, currentIndex + 2);
  int skipCurrent = solveUsingRecursion(houses, currentIndex + 1);

  return max(robCurrent, skipCurrent);
}

Time Complexity: (O(2^n)) — Exponential time because it explores all possible combinations.

Space Complexity: (O(n)) — The space complexity is due to the recursion stack.

2. Memoization Solution
The recursive solution has overlapping subproblems, meaning it solves the same subproblem multiple times. We can optimize this using memoization, where we store the results of subproblems in a dp array and reuse them when needed.

int solveUsingMemoization(const vector<int> &houses, int currentIndex, vector<int> &dp) {
  if (currentIndex >= houses.size()) {
    return 0;
  }

  if (dp[currentIndex] != -1) {
    return dp[currentIndex];
  }

  int robCurrent = houses[currentIndex] + solveUsingMemoization(houses, currentIndex + 2, dp);
  int skipCurrent = solveUsingMemoization(houses, currentIndex + 1, dp);

  dp[currentIndex] = max(robCurrent, skipCurrent);
  return dp[currentIndex];
}

Time Complexity: O(n) — Each subproblem is solved only once.

Space Complexity: O(n) — Space is needed for both the dp array and the recursion stack.

3. Tabulation Solution
The tabulation approach eliminates recursion by building the solution iteratively from the base case. We maintain a dp array where each entry represents the maximum money that can be robbed up to that house.

int solveUsingTabulation(const vector<int> &houses) {
  if (houses.empty()) {
    return 0;
  }

  vector<int> maxRobbableAmounts(houses.size(), -1);
  maxRobbableAmounts[houses.size() - 1] = houses.back();

  for (int i = houses.size() - 2; i >= 0; i--) {
    int robCurrent = houses[i] + (i + 2 < houses.size() ? maxRobbableAmounts[i + 2] : 0);
    int skipCurrent = maxRobbableAmounts[i + 1];
    maxRobbableAmounts[i] = max(robCurrent, skipCurrent);
  }

  return maxRobbableAmounts[0];
}

Time Complexity: O(n) — Iterates through the houses list once.

Space Complexity: O(n) — Space is required for the dp array.

4. Space-Optimized Tabulation Solution
The tabulation approach can be further optimized by realizing that the result at each house only depends on the results from the next two houses. Therefore, instead of maintaining a full dp array, we only need three variables to track the necessary results.

int solveUsingSpaceOptimizedTabulation(const vector<int> &houses) {
  if (houses.empty()) {
    return 0;
  }

  int previousAmount = houses.back();
  int nextAmount = 0;
  int currentAmount = 0;

  for (int i = houses.size() - 2; i >= 0; i--) {
    int robCurrent = houses[i] + nextAmount;
    int skipCurrent = previousAmount;

    currentAmount = max(robCurrent, skipCurrent);

    nextAmount = previousAmount;
    previousAmount = currentAmount;
  }

  return previousAmount;
}

Time Complexity: O(n) — Same as tabulation.

Space Complexity: O(1) — Constant space is used for three variables.

Conclusion
The House Robber problem is an excellent example of how dynamic programming can be used to optimize recursive solutions. We started with a simple recursive approach and progressively optimized it by using memoization, tabulation, and finally, a space-optimized solution. Each step reduced the time and space complexity, making the solution more efficient.