House Robber medium

Problem Statement

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 a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: nums = [1,2,3,1] Output: 4 Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 1). 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.

Steps

1. Base Cases: If the input array is empty, return 0. If the array has only one house, return the amount in that house.

2. Dynamic Programming: We can use dynamic programming to solve this problem efficiently. Create a DP array dp of the same size as the input array nums. dp[i] will store the maximum amount of money that can be robbed up to house i (inclusive).

3. Iteration: Iterate through the nums array. For each house i:

   • If i == 0, dp[i] = nums[i] (only one house).
   • If i == 1, dp[i] = max(nums[0], nums[1]) (choose the larger of the first two houses).
   • If i > 1, dp[i] = max(dp[i-1], dp[i-2] + nums[i]). This represents the choice: either rob the current house (dp[i-2] + nums[i]) or skip it and take the maximum from the previous houses (dp[i-1]).

4. Return: After iterating through all houses, dp[nums.size() - 1] will contain the maximum amount of money that can be robbed.

Explanation

The dynamic programming approach works because it breaks down the problem into smaller overlapping subproblems. dp[i] depends on the solutions to dp[i-1] and dp[i-2]. By solving these smaller subproblems and storing their solutions, we avoid redundant calculations. The max function ensures we always choose the optimal solution at each step.

Code

#include <vector>
#include <algorithm>

using namespace std;

int rob(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;
    if (n == 1) return nums[0];

    vector<int> dp(n);
    dp[0] = nums[0];
    dp[1] = max(nums[0], nums[1]);

    for (int i = 2; i < n; ++i) {
        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
    }

    return dp[n - 1];
}

Complexity

• Time Complexity: O(n), where n is the number of houses. We iterate through the array once.
• Space Complexity: O(n), due to the dp array. This can be optimized to O(1) by using only two variables to store the previous two maximum amounts instead of the entire array. (See optimized code below)

Optimized Code (O(1) Space)

#include <vector>
#include <algorithm>

using namespace std;

int rob(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;
    if (n == 1) return nums[0];

    int prev1 = nums[0];
    int prev2 = max(nums[0], nums[1]);

    for (int i = 2; i < n; ++i) {
        int current = max(prev2, prev1 + nums[i]);
        prev1 = prev2;
        prev2 = current;
    }

    return prev2;
}

This optimized version achieves the same result with constant space complexity.