House Robber

Why it belongs on this sheet

This is one of the most reusable DP patterns: at each position, either take the current option or skip it.

Pattern

Take or skip

Approach

For each house, the best answer is either the previous best without this house, or the best up to two houses back plus this house's money.

Java solution

class Solution {
  public int rob(int[] nums) {
    int robPrev = 0;
    int skipPrev = 0;

    for (int num : nums) {
      int newRob = skipPrev + num;
      skipPrev = Math.max(skipPrev, robPrev);
      robPrev = newRob;
    }

    return Math.max(robPrev, skipPrev);
  }
}

Complexity

• Time: O(n)
• Space: O(1)

Interview note

If the variable names feel abstract, phrase it as "best including current" and "best excluding current."