14.15 House Robber

14.15.1 Problem Metadata

14.15.2 Description

Given a lc-list of non-negative integers representing the amount of money in each house along a street, determine the maximum amount you can rob without robbing two adjacent houses.

14.15.3 Examples

Input: [1,2,3,1]
Output: 4

14.15.4 Constraints

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 400

14.15.5 Solution - Linear DP

14.15.5.1 Walkthrough

Let dp[i] be the best we can do up to house i. For each house, we either rob it plus dp[i-2] or skip it and take dp[i-1]. Initialize the first two values and iterate.

14.15.5.2 Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(1) using rolling variables

14.15.5.3 Implementation Steps

  1. Handle n == 1.
  2. Maintain prev2 (dp[i-2]) and prev1 (dp[i-1]).
  3. For each house value num, compute current = Math.max(prev1, prev2 + num).
  4. Shift prev2 = prev1, prev1 = current.
  5. Return prev1.

14.15.5.4 Code - Java

public int rob(int[] nums) {
    if (nums.length == 1) {
        return nums[0];
    }

    int prev2 = 0;
    int prev1 = 0;

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

    return prev1;
}