198. House Robber

Description

The problem is to determine the maximum amount of money you can rob from a series of houses, where you cannot rob two adjacent houses.

Intuition

If you rob a house, you cannot rob the house immediately following it. This means that for each house, you have two choices: either rob it and add its value to the total from two houses before, or skip it and take the total from the house before. This forms the basis of a dynamic programming solution.

Approach

1. Base Cases: - If there is only one house, rob it. - Create a dynamic programming array dp where dp[i] represents the maximum amount of money that can be robbed up to the ith house.
2. Initialize: - Set dp[0] to nums[0]. - Set dp[1] to the maximum of nums[0] and nums[1].
3. Iterate and Fill: - For each house from 2 to n-1, set dp[i] to the maximum of dp[i-1] (skipping the current house) and nums[i] + dp[i-2] (robbing the current house).
4. Result: - The value at dp[n-1] will be the maximum amount of money that can be robbed.

Complexity

Time Complexity:

O(n), since we are iterating through the houses once.

Space Complexity:

O(n), due to the dp array that stores the maximum money that can be robbed up to each house.

Code

C++

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

Python

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return nums[0]
        dp = [0] * n
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])
        for i in range(2, n):
            dp[i] = max(dp[i - 1], nums[i] + dp[i - 2])
        return dp[n - 1]

Java

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

JavaScript

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