198. House Robber

Medium

Problem Description

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Examples

Example 1:
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

Example 2:
Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.
Jump to Solution: Python Java C++ JavaScript C#

Python Solution


def rob(nums: List[int]) -> int:
    if not nums:
        return 0
    if len(nums) <= 2:
        return max(nums)
    
    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-1], dp[i-2] + nums[i])
    
    return dp[-1]

Space-Optimized Solution:


def rob(nums: List[int]) -> int:
    rob1, rob2 = 0, 0
    
    for num in nums:
        temp = max(rob1 + num, rob2)
        rob1 = rob2
        rob2 = temp
    
    return rob2

Java Solution


class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums.length <= 2) {
            return nums.length == 1 ? nums[0] : Math.max(nums[0], nums[1]);
        }
        
        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-1], dp[i-2] + nums[i]);
        }
        
        return dp[nums.length - 1];
    }
}

C++ Solution


class Solution {
public:
    int rob(vector& nums) {
        if (nums.empty()) {
            return 0;
        }
        if (nums.size() <= 2) {
            return nums.size() == 1 ? nums[0] : max(nums[0], nums[1]);
        }
        
        vector dp(nums.size());
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        
        for (int i = 2; i < nums.size(); i++) {
            dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
        }
        
        return dp.back();
    }
};

JavaScript Solution


/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    if (!nums.length) {
        return 0;
    }
    if (nums.length <= 2) {
        return Math.max(...nums);
    }
    
    let rob1 = 0;
    let rob2 = 0;
    
    for (const num of nums) {
        const temp = Math.max(rob1 + num, rob2);
        rob1 = rob2;
        rob2 = temp;
    }
    
    return rob2;
};

C# Solution


public class Solution {
    public int Rob(int[] nums) {
        if (nums == null || nums.Length == 0) {
            return 0;
        }
        if (nums.Length <= 2) {
            return nums.Length == 1 ? nums[0] : Math.Max(nums[0], nums[1]);
        }
        
        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-1], dp[i-2] + nums[i]);
        }
        
        return dp[nums.Length - 1];
    }
}

Complexity Analysis

Solution Explanation

This is a dynamic programming problem that can be solved in two ways:

Key Points

State Transition

The core of the solution is the state transition equation:

dp[i] = max(dp[i-1], dp[i-2] + nums[i])

This represents the choice at each house: