LeetCode 198: House Robber (Dynamic Programming)

Today we solve LeetCode 198 - House Robber.

Source: https://leetcode.com/problems/house-robber/

English

Problem Summary

You are given an integer array nums where each value is the cash in one house. Adjacent houses cannot both be robbed. Return the maximum money you can steal without alerting the police.

Key Insight

At each index i, you only choose between two states: skip this house (keep previous best) or rob this house (best up to i-2 plus nums[i]). This naturally forms a 1D DP transition.

Brute Force and Limitations

Brute force explores every valid subset with recursion: rob current and jump to i+2, or skip and move to i+1. This becomes exponential (O(2^n)) and quickly times out.

Optimal Algorithm Steps

1) Let prev2 be best result up to house i-2, and prev1 be best up to i-1.
2) For each value x in nums, compute cur = max(prev1, prev2 + x).
3) Shift states: prev2 = prev1, prev1 = cur.
4) After traversal, prev1 is the answer.

Complexity Analysis

Time: O(n).
Space: O(1) with rolling states.

Common Pitfalls

- Wrong base handling for empty array.
- Accidentally using prev1 + nums[i] (which violates adjacency).
- State update order mistakes (overwrite before using old values).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int rob(int[] nums) {
        int prev2 = 0;
        int prev1 = 0;

        for (int x : nums) {
            int cur = Math.max(prev1, prev2 + x);
            prev2 = prev1;
            prev1 = cur;
        }

        return prev1;
    }
}

func rob(nums []int) int {
    prev2, prev1 := 0, 0

    for _, x := range nums {
        cur := prev1
        if prev2+x > cur {
            cur = prev2 + x
        }
        prev2 = prev1
        prev1 = cur
    }

    return prev1
}

class Solution {
public:
    int rob(vector<int>& nums) {
        int prev2 = 0, prev1 = 0;
        for (int x : nums) {
            int cur = max(prev1, prev2 + x);
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
};

class Solution:
    def rob(self, nums):
        prev2, prev1 = 0, 0

        for x in nums:
            cur = max(prev1, prev2 + x)
            prev2, prev1 = prev1, cur

        return prev1

var rob = function(nums) {
  let prev2 = 0;
  let prev1 = 0;

  for (const x of nums) {
    const cur = Math.max(prev1, prev2 + x);
    prev2 = prev1;
    prev1 = cur;
  }

  return prev1;
};

中文

题目概述

给定数组 nums，每个元素表示一间房子的金额。相邻房子不能同时偷，求在不触发警报的前提下可偷到的最大金额。

核心思路

对每个位置 i，只有两种选择：不偷当前房子（沿用 i-1 的最优值）或偷当前房子（拿 i-2 的最优值 + nums[i]）。这是典型的一维 DP 转移。

暴力解法与不足

暴力递归会枚举“偷/不偷”所有分支，复杂度接近 O(2^n)，输入稍大就会超时。

最优算法步骤

1）维护滚动状态：prev2（到 i-2 的最优）、prev1（到 i-1 的最优）。
2）遍历当前金额 x，计算 cur = max(prev1, prev2 + x)。
3）状态前移：prev2 = prev1，prev1 = cur。
4）遍历结束，返回 prev1。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。

常见陷阱

- 忘记处理空数组。
- 把“偷当前”写成 prev1 + nums[i]（会违反相邻限制）。
- 更新状态顺序错误，导致旧值被覆盖。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int rob(int[] nums) {
        int prev2 = 0;
        int prev1 = 0;

        for (int x : nums) {
            int cur = Math.max(prev1, prev2 + x);
            prev2 = prev1;
            prev1 = cur;
        }

        return prev1;
    }
}

func rob(nums []int) int {
    prev2, prev1 := 0, 0

    for _, x := range nums {
        cur := prev1
        if prev2+x > cur {
            cur = prev2 + x
        }
        prev2 = prev1
        prev1 = cur
    }

    return prev1
}

class Solution {
public:
    int rob(vector<int>& nums) {
        int prev2 = 0, prev1 = 0;
        for (int x : nums) {
            int cur = max(prev1, prev2 + x);
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
};

class Solution:
    def rob(self, nums):
        prev2, prev1 = 0, 0

        for x in nums:
            cur = max(prev1, prev2 + x)
            prev2, prev1 = prev1, cur

        return prev1

var rob = function(nums) {
  let prev2 = 0;
  let prev1 = 0;

  for (const x of nums) {
    const cur = Math.max(prev1, prev2 + x);
    prev2 = prev1;
    prev1 = cur;
  }

  return prev1;
};