House Robber

Problem Statement

You’re a stealthy thief hitting a row of houses, each with some cash. You can’t rob adjacent houses due to security systems. Maximize your loot! This medium-level DP challenge is a heist planner’s dream—pick your targets wisely!

Example

Input: nums = [1, 2, 3, 1]

Output: 4 (rob 1+3)

Input: nums = [2, 7, 9, 3, 1]

Output: 12 (rob 2+9+1)

Input: nums = [2, 1, 1, 2]

Output: 4 (rob 2+2)

Code

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

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

# Example usage
print(rob([1, 2, 3, 1]))  # 4
print(rob([2, 7, 9, 3, 1]))  # 12
            

function rob(nums) {
    if (!nums.length) return 0;
    if (nums.length === 1) return nums[0];
    let dp = new Array(nums.length);
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1]);
    for (let i = 2; i < nums.length; i++) {
        dp[i] = Math.max(dp[i-2] + nums[i], dp[i-1]);
    }
    return dp[nums.length-1];
}

// Example usage
console.log(rob([1, 2, 3, 1]));  // 4
console.log(rob([2, 7, 9, 3, 1]));  // 12
            

Explanation

• DP Insight: At each house, choose max of robbing it (plus loot from 2 houses back) or skipping it.
• Steps: dp[0] = first house, dp[1] = max of first two, then dp[i] = max(dp[i-2] + nums[i], dp[i-1]).
• Flow Example ([2,7,9,3,1]): dp[0]=2, dp[1]=7, dp[2]=11 (2+9), dp[3]=11, dp[4]=12 (11+1).
• Why It Works: Optimal substructure—each decision builds on prior max loot.

Note