The House Robber Algorithm

The House Robber problem is a classic dynamic programming challenge where you must find the maximum amount of money you can rob from a row of houses without robbing two adjacent houses.

The Core Problem

YouImagine a street with several houses, each containing a certain amount of money. Your goal is to maximize the total money stolen, but with one critical constraint: you cannot rob two adjacent houses. This means if you rob House `i`, you cannot rob House `i-1` or House `i+1`.

Making Decisions at Each House

For each house, you have two choices:

1. Rob the current house: If you choose to rob House `i`, you cannot have robbed House `i-1`. Your total profit would be the money in House `i` plus the maximum profit you could have made up to House `i-2`. 2. Skip the current house: If you choose to skip House `i`, your total profit remains the same as the maximum profit you could have made up to House `i-1`.

At each step, you must pick the option that yields the greater profit.

Dynamic Programming Approach

This problem is perfectly suited for dynamic programming because optimal substructures and overlapping subproblems exist. We can build up the solution by storing the maximum profit achievable up to each house.

Let `dp[i]` be the maximum money that can be robbed from houses `0` to `i`.

function rob(nums):
  if nums is empty: return 0
  if nums has one house: return nums[0]

  dp = array of size nums.length
  dp[0] = nums[0]
  dp[1] = max(nums[0], nums[1])

  for i from 2 to nums.length - 1:
    dp[i] = max(dp[i-1], nums[i] + dp[i-2])

  return dp[nums.length - 1]

Base Cases

To start, we need to handle the first two houses:

• If there's only one house, you rob it.
• If there are two houses, you rob the one with more money.

These form the base cases for our `dp` array. For subsequent houses, we apply the decision logic: `dp[i] = max(dp[i-1], nums[i] + dp[i-2])`.

Efficiency

This dynamic programming solution has a time complexity of O(n) because we iterate through the houses once. The space complexity is also O(n) to store the `dp` array. This approach trades memory for speed, avoiding redundant calculations.

Key Takeaways

• The House Robber problem requires maximizing profit without robbing adjacent houses.
• At each house, you decide to either rob it (adding its value to the profit from two houses back) or skip it (keeping the profit from the previous house).
• Dynamic programming is used to store the maximum profit up to each house.
• The solution has O(n) time and O(n) space complexity.
• The final answer is the maximum profit stored for the last house.