#51 · 1D DP

House Robber

Given the amount of money in each house along a street, return the maximum you can rob without robbing two adjacent houses.

MediumLeetCode

Computing
Depends on
Answer

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

One-dimensional DP table

dp[i] = the best total from houses i onward. The decision at house i is binary (rob or skip) and each branch reduces to a smaller suffix, so one array indexed by position holds all sub-answers.

Memory layout

A flat array of n + 2 numbers (two zero cells beyond the end). Because only dp[i + 1] and dp[i + 2] are read, two variables are enough.

Operation	Cost
time	O(n)
space	O(n) table, O(1) with two variables

Include / exclude recurrence

best(i) = max(nums[i] + best(i + 2), best(i + 1)). Robbing house i forbids i + 1, so you resume at i + 2; skipping it leaves i + 1 free.

Memory layout

No data structure: a formula over two earlier answers.

Operation	Cost
per cell	O(1)

Why it fits

The question asks for an optimum over choices, and a choice at one house only interacts with its neighbour: the classic shape for dynamic programming.
The sub-problems (best from house i onward) overlap heavily, so computing each exactly once turns an exponential search into a linear pass.
Each answer depends on just the next two, so the full table is not needed and a rolling pair of variables is enough.

Why alternatives degrade

Greedy: always take the biggest house:: For 2, 7, 9, 3, 1 picking 9 first gives 9 + 2 or 9 + 1 = at most 11 but the best is 12 (2 + 9 + 1). A local choice can block a better total.
Take every other house:: The best pattern need not alternate: sometimes you skip two houses in a row, as in 2, 1, 1, 2 (take both 2s).
Sorting by value:: The adjacency constraint depends on positions, which sorting throws away.

Four approaches, from naive to production

1 · beginner

Recursion: rob it or skip it

time O(2ⁿ)space O(n) recursion

At house i either take its money and jump to house i + 2, or skip it and continue at house i + 1. The best total is the larger of the two outcomes; past the last house the total is 0.

int rob(vector<int>& nums) {
    function<int(int)> best = [&](int i) -> int {
        if (i >= (int)nums.size()) return 0;
        return max(nums[i] + best(i + 2), best(i + 1));
    };
    return best(0);
}

public int rob(int[] nums) {
    return best(nums, 0);
}
private int best(int[] nums, int i) {
    if (i >= nums.length) return 0;
    return Math.max(nums[i] + best(nums, i + 2), best(nums, i + 1));
}

def rob(nums):
    def best(i):
        if i >= len(nums): return 0
        return max(nums[i] + best(i + 2), best(i + 1))
    return best(0)

function rob(nums: number[]): number {
  const best = (i: number): number => {
    if (i >= nums.length) return 0;
    return Math.max(nums[i] + best(i + 2), best(i + 1));
  };
  return best(0);
}

Flaws & bottlenecks

The same suffix is solved many times (best(3) is reached through best(1) and best(2)).
The number of calls grows like the Fibonacci numbers.
Recursion depth is n.

Interviewer cross-questions

Why jump to i + 2 when robbing?

Say: Robbing house i makes house i + 1 forbidden (it is adjacent), so the next house you may consider is i + 2.

Where does the repetition come from?

Say: Different earlier choices lead to the same remaining suffix. Rob 0 then skip 1, or skip 0 then rob 1... both can reach best(3).

How do you remove the repetition?

Say: Store each best(i) once (memoisation) or fill the answers from the end of the street backwards.

2 · intermediate

Memoised recursion

time O(n)space O(n)

Keep the recursion and add a memo array initialised with -1. If memo[i] is known return it; otherwise compute the best of rob/skip, store it, and return it.

int rob(vector<int>& nums) {
    vector<int> memo(nums.size(), -1);
    function<int(int)> best = [&](int i) -> int {
        if (i >= (int)nums.size()) return 0;
        if (memo[i] != -1) return memo[i];
        memo[i] = max(nums[i] + best(i + 2), best(i + 1));
        return memo[i];
    };
    return best(0);
}

public int rob(int[] nums) {
    int[] memo = new int[nums.length];
    Arrays.fill(memo, -1);
    return best(nums, memo, 0);
}
private int best(int[] nums, int[] memo, int i) {
    if (i >= nums.length) return 0;
    if (memo[i] != -1) return memo[i];
    memo[i] = Math.max(nums[i] + best(nums, memo, i + 2), best(nums, memo, i + 1));
    return memo[i];
}

def rob(nums):
    memo = [-1] * len(nums)
    def best(i):
        if i >= len(nums): return 0
        if memo[i] != -1: return memo[i]
        memo[i] = max(nums[i] + best(i + 2), best(i + 1))
        return memo[i]
    return best(0)

function rob(nums: number[]): number {
  const memo = new Array<number>(nums.length).fill(-1);
  const best = (i: number): number => {
    if (i >= nums.length) return 0;
    if (memo[i] !== -1) return memo[i];
    memo[i] = Math.max(nums[i] + best(i + 2), best(i + 1));
    return memo[i];
  };
  return best(0);
}

Flaws & bottlenecks

Still recursive: depth up to n.
The memo array needs a sentinel (-1) that must not be a valid answer (amounts are non-negative, so it is safe here).
Function-call overhead per house.

Interviewer cross-questions

Why does memoisation make it O(n)?

Say: There are only n different values of i. Each is computed once, and every later call is a constant-time lookup.

Why can -1 mark "unknown"?

Say: The best total is never negative, so -1 cannot be a real answer. If values could be negative you would need a separate flag or an optional value.

What is the downside versus a loop?

Say: Recursion depth equals the number of houses, which can overflow the stack for very long streets, and the calls cost more than a simple loop.

3 · advanced

Bottom-up table from the last house

time O(n)space O(n)

Fill dp from the right: dp[i] = max(nums[i] + dp[i + 2], dp[i + 1]), with two zero cells past the end. The answer is dp[0].

int rob(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n + 2, 0);
    for (int i = n - 1; i >= 0; i--) {
        dp[i] = max(nums[i] + dp[i + 2], dp[i + 1]);
    }
    return dp[0];
}

public int rob(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n + 2];
    for (int i = n - 1; i >= 0; i--) {
        dp[i] = Math.max(nums[i] + dp[i + 2], dp[i + 1]);
    }
    return dp[0];
}

def rob(nums):
    n = len(nums)
    dp = [0] * (n + 2)
    for i in range(n - 1, -1, -1):
        dp[i] = max(nums[i] + dp[i + 2], dp[i + 1])
    return dp[0]

function rob(nums: number[]): number {
  const n = nums.length;
  const dp = new Array<number>(n + 2).fill(0);
  for (let i = n - 1; i >= 0; i--) {
    dp[i] = Math.max(nums[i] + dp[i + 2], dp[i + 1]);
  }
  return dp[0];
}

Flaws & bottlenecks

O(n) memory for values that are only used a couple of steps later.
The two padding cells are easy to forget or to size wrong (an off-by-one gives wrong answers for tiny inputs).
An empty input needs a guard in some languages (here the loop simply does not run and dp[0] is 0).

Interviewer cross-questions

Why fill from the right?

Say: dp[i] depends on higher indices, so going from n − 1 down to 0 guarantees they are final when needed.

Why two extra cells?

Say: The last house reads dp[n] and dp[n + 1]. Both mean "no houses left" and are 0, which removes special cases from the loop.

Can it run left to right?

Say: Yes, with the mirrored recurrence dp[i] = max(dp[i − 1], dp[i − 2] + nums[i]); the result is the same.

4 · expert

Two rolling variables

time O(n)space O(1)

Keep only next1 (best from house i + 1) and next2 (best from house i + 2). For each house compute cur = max(nums[i] + next2, next1), then shift: next2 = next1, next1 = cur.

int rob(vector<int>& nums) {
    int next1 = 0, next2 = 0;
    for (int i = (int)nums.size() - 1; i >= 0; i--) {
        int cur = max(nums[i] + next2, next1);
        next2 = next1;
        next1 = cur;
    }
    return next1;
}

public int rob(int[] nums) {
    int next1 = 0, next2 = 0;
    for (int i = nums.length - 1; i >= 0; i--) {
        int cur = Math.max(nums[i] + next2, next1);
        next2 = next1;
        next1 = cur;
    }
    return next1;
}

def rob(nums):
    next1 = next2 = 0
    for i in range(len(nums) - 1, -1, -1):
        cur = max(nums[i] + next2, next1)
        next2 = next1
        next1 = cur
    return next1

function rob(nums: number[]): number {
  let next1 = 0, next2 = 0;
  for (let i = nums.length - 1; i >= 0; i--) {
    const cur = Math.max(nums[i] + next2, next1);
    next2 = next1;
    next1 = cur;
  }
  return next1;
}

Flaws & bottlenecks

The history is lost: you cannot reconstruct which houses were robbed without extra bookkeeping.
The three-line shift is easy to reorder wrongly (assigning next1 before reading it).
Offers no early exit; every house is visited.

Interviewer cross-questions

How would you also return the chosen houses?

Say: Keep the full table (or a parent flag per house) and walk back from dp[0]: if dp[i] came from the rob branch, house i is in the set and the walk continues at i + 2; otherwise at i + 1.

Why does the order of the three assignments matter?

Say: cur must be computed from the old next1 and next2 before either changes; next2 must take the old next1 before next1 takes cur.

Is O(1) space always possible for DP?

Say: Only when each state reads a bounded number of previous states, as here (two). Problems whose states read arbitrary earlier ones, such as longest increasing subsequence, need the table.

Synchronized code walkthrough

Showing: Recursion: rob it or skip it — shares the player above; click any step to jump.

int rob(vector<int>& nums) {
    function<int(int)> best = [&](int i) -> int {
        if (i >= (int)nums.size()) return 0;
        return max(nums[i] + best(i + 2), best(i + 1));
    };
    return best(0);
}

public int rob(int[] nums) {
    return best(nums, 0);
}
private int best(int[] nums, int i) {
    if (i >= nums.length) return 0;
    return Math.max(nums[i] + best(nums, i + 2), best(nums, i + 1));
}

def rob(nums):
    def best(i):
        if i >= len(nums): return 0
        return max(nums[i] + best(i + 2), best(i + 1))
    return best(0)

function rob(nums: number[]): number {
  const best = (i: number): number => {
    if (i >= nums.length) return 0;
    return Math.max(nums[i] + best(i + 2), best(i + 1));
  };
  return best(0);
}

int rob(vector<int>& nums) {
    vector<int> memo(nums.size(), -1);
    function<int(int)> best = [&](int i) -> int {
        if (i >= (int)nums.size()) return 0;
        if (memo[i] != -1) return memo[i];
        memo[i] = max(nums[i] + best(i + 2), best(i + 1));
        return memo[i];
    };
    return best(0);
}

public int rob(int[] nums) {
    int[] memo = new int[nums.length];
    Arrays.fill(memo, -1);
    return best(nums, memo, 0);
}
private int best(int[] nums, int[] memo, int i) {
    if (i >= nums.length) return 0;
    if (memo[i] != -1) return memo[i];
    memo[i] = Math.max(nums[i] + best(nums, memo, i + 2), best(nums, memo, i + 1));
    return memo[i];
}

def rob(nums):
    memo = [-1] * len(nums)
    def best(i):
        if i >= len(nums): return 0
        if memo[i] != -1: return memo[i]
        memo[i] = max(nums[i] + best(i + 2), best(i + 1))
        return memo[i]
    return best(0)

function rob(nums: number[]): number {
  const memo = new Array<number>(nums.length).fill(-1);
  const best = (i: number): number => {
    if (i >= nums.length) return 0;
    if (memo[i] !== -1) return memo[i];
    memo[i] = Math.max(nums[i] + best(i + 2), best(i + 1));
    return memo[i];
  };
  return best(0);
}

int rob(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n + 2, 0);
    for (int i = n - 1; i >= 0; i--) {
        dp[i] = max(nums[i] + dp[i + 2], dp[i + 1]);
    }
    return dp[0];
}

public int rob(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n + 2];
    for (int i = n - 1; i >= 0; i--) {
        dp[i] = Math.max(nums[i] + dp[i + 2], dp[i + 1]);
    }
    return dp[0];
}

def rob(nums):
    n = len(nums)
    dp = [0] * (n + 2)
    for i in range(n - 1, -1, -1):
        dp[i] = max(nums[i] + dp[i + 2], dp[i + 1])
    return dp[0]

function rob(nums: number[]): number {
  const n = nums.length;
  const dp = new Array<number>(n + 2).fill(0);
  for (let i = n - 1; i >= 0; i--) {
    dp[i] = Math.max(nums[i] + dp[i + 2], dp[i + 1]);
  }
  return dp[0];
}

int rob(vector<int>& nums) {
    int next1 = 0, next2 = 0;
    for (int i = (int)nums.size() - 1; i >= 0; i--) {
        int cur = max(nums[i] + next2, next1);
        next2 = next1;
        next1 = cur;
    }
    return next1;
}

public int rob(int[] nums) {
    int next1 = 0, next2 = 0;
    for (int i = nums.length - 1; i >= 0; i--) {
        int cur = Math.max(nums[i] + next2, next1);
        next2 = next1;
        next1 = cur;
    }
    return next1;
}

def rob(nums):
    next1 = next2 = 0
    for i in range(len(nums) - 1, -1, -1):
        cur = max(nums[i] + next2, next1)
        next2 = next1
        next1 = cur
    return next1

function rob(nums: number[]): number {
  let next1 = 0, next2 = 0;
  for (let i = nums.length - 1; i >= 0; i--) {
    const cur = Math.max(nums[i] + next2, next1);
    next2 = next1;
    next1 = cur;
  }
  return next1;
}