LeetCode 198 · Dynamic Programming

House Robber

MediumMax loot without robbing two adjacent houses — the classic take-or-skip DP.
You are given an array nums where nums[i] is the money in house i. You cannot rob two adjacent houses (that triggers the alarm). Return the maximum amount you can rob.

Walkthrough

try:
Rob houses for the most money, but never two adjacent ones. dp[i] = best loot considering houses up to i.
house 0
house 1
house 2
house 3
nums
1
2
3
1
dp
·
·
·
·
1
function rob(nums) {
2
  const n = nums.length;
3
  if (n === 0) return 0;
4
  const dp = new Array(n).fill(0);
◄
5
  dp[0] = nums[0];
6
  for (let i = 1; i < n; i++) {
7
    const rob  = (i >= 2 ? dp[i-2] : 0) + nums[i];
8
    const skip = dp[i-1];
9
    dp[i] = Math.max(rob, skip);
10
  }
11
  return dp[n-1];
12
}
step 0 / 11
line 4
dp[i] = best loot through house i
dp[i] is the most money robbable from houses 0..i without triggering two adjacent alarms.

Intuition

At every house you face one binary choice: rob it, or skip it. That choice is all the state you need.

If you ROB house i, you cannot have robbed i − 1, so your total is dp[i − 2] + nums[i]. If you SKIP it, your total is just the best through i − 1, i.e. dp[i − 1].

So dp[i] = max(dp[i − 2] + nums[i], dp[i − 1]) — each house only ever looks two steps back.

Seed it with dp[0] = nums[0], and the last dp value is the answer. (Since only two previous values matter, this can be squeezed to O(1) space with two rolling variables.)

The algorithm

  1. 01dp[i] = the most money robbable considering houses 0..i.
  2. 02Base: dp[0] = nums[0].
  3. 03For each i ≥ 1: take = dp[i−2] + nums[i], skip = dp[i−1].
  4. 04dp[i] = max(take, skip); return dp[n−1].

Reference implementation

1
function rob(nums) {
2
  const n = nums.length;
3
  if (n === 0) return 0;
4
  const dp = new Array(n).fill(0);      // dp[i] = best loot through house i
5
  dp[0] = nums[0];
6
  for (let i = 1; i < n; i++) {
7
    const take = (i >= 2 ? dp[i - 2] : 0) + nums[i];   // rob i, so skip i-1
8
    const skip = dp[i - 1];                            // skip i
9
    dp[i] = Math.max(take, skip);
10
  }
11
  return dp[n - 1];
12
}

Complexity

Time
O(n) — one pass.
Space
O(n) for the dp array (O(1) with rolling variables).