DP 5. Maximum Sum of Non-Adjacent Elements (House Robber) | 1-D | DP on Subsequences

This comprehensive guide explores the classic Maximum Sum of Non-Adjacent Elements problem (commonly known as House Robber). We will build an optimal solution using a 1-D Dynamic Programming approach on subsequences, evolving step-by-step from naive recursion to memoization, tabulation, and ultimate space optimization.

1. Why Do We Need This? (Problem Statement & Status Quo)

We are given an array of $N$ integers representing values at each index (e.g., money stashed in houses along a street). Our goal is to return the maximum sum of a subsequence with one strict operational constraint: no two elements in our chosen subsequence can be adjacent in the original array.

• Status Quo / Naive Thinking: If we try to brute-force all possible subsequences to verify the condition and calculate sums, the combinatorial explosion leads to exponential time complexity ($O(2^N)$).
• The Core Challenge: How do we efficiently explore valid subsequences while skipping adjacent elements without re-computing overlapping subproblems?

Real-Life Analogy: The House Robber

Imagine walking down a street where every house has a certain amount of cash. If you rob a house, the security alarm automatically triggers if you also rob its immediate neighbor (house on the left or right). Therefore, you want to pick a subset of non-adjacent houses that maximizes your total loot without getting caught.

2. Core Mental Model: The "Pick and Non-Pick" Technique

To generate all valid subsequences, we rely on the foundational Pick / Non-Pick framework used across recursion and dynamic programming on subsequences:

1. Express the problem in terms of an index: We evaluate the array starting from the last index ($N-1$) down to $0$.
2. Make a decision at the current index:
   • Pick (Take): Include the current element's value in our running sum. Because we picked this element, we cannot pick the adjacent element immediately before it. Thus, we must jump directly to index - 2.
   • Non-Pick (Skip): Skip the current element entirely. Because we did not pick it, we are completely safe to consider the immediately preceding element at index - 1.
3. Return the best choice: Take the mathematical max() between the Pick branch and the Non-Pick branch.

3. Step-by-Step Transition & Recurrence Relation

Let $f(\text{index})$ represent the maximum sum of a subsequence with no adjacent elements from index $0$ up to the given index.

Recurrence Breakdown

• Pick Branch: nums[index] + f(index - 2)
• Non-Pick Branch: 0 + f(index - 1)
• Transition Formula:

Base Cases

1. When index == 0: If recursion reaches index 0, it means index 1 was not picked (otherwise we would have jumped past 0). Since the array contains non-negative numbers, we must pick index 0 to maximize our sum. Therefore, return nums[0].
2. When index < 0: If recursion falls out of bounds below zero (via index - 2), there are no elements left to pick. Therefore, return 0.

4. Naive Recursion vs. Memoization (Overlapping Subproblems)

If we implement pure recursion, the same subproblems are solved repeatedly, creating an exponential time complexity tree.

Proving Overlapping Subproblems

When calculating the maximum sum for an array like [2, 1, 4, 9] at f(3), the recursion tree branches into f(1) and f(2). Both branches independently need to compute lower states like f(1) multiple times.

We can eliminate this redundancy by introducing Memoization—storing computed states in a 1-D DP array initialized to -1.

Memoized Implementation (C++)

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
private:
    int solveMemo(int index, vector<int>& nums, vector<int>& dp) {
        // Base Cases
        if (index == 0) return nums[0];
        if (index < 0) return 0;
        
        // Return precomputed state if available
        if (dp[index] != -1) return dp[index];
        
        // Pick current element and jump 2 steps back
        int pick = nums[index] + solveMemo(index - 2, nums, dp);
        
        // Do not pick current element and jump 1 step back
        int nonPick = 0 + solveMemo(index - 1, nums, dp);
        
        // Store and return the maximum of both choices
        return dp[index] = max(pick, nonPick);
    }

public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        vector<int> dp(n, -1);
        return solveMemo(n - 1, nums, dp);
    }
};

• Time Complexity: $O(N)$ because each state from $0$ to $N-1$ is computed only once.
• Space Complexity: $O(N)$ for the memoization table plus $O(N)$ for the recursive stack space.

5. Tabulation Approach (Bottom-Up DP)

We can remove auxiliary stack space by converting our top-down memoized recursion into a bottom-up tabulation loop.

Tabulation Logic

1. Create a DP table of size $N$: vector<int> dp(n)
2. Set the base case: dp[0] = nums[0]
3. Iterate from i = 1 up to n - 1:
   • Compute take: nums[i] + (i > 1 ? dp[i - 2] : 0)
   • Compute nonTake: 0 + dp[i - 1]
   • Store maximum in dp[i] = max(take, nonTake)

Tabulated Implementation (C++)

int robTabulation(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;
    if (n == 1) return nums[0];
    
    vector<int> dp(n, 0);
    dp[0] = nums[0];
    
    for (int i = 1; i < n; i++) {
        int take = nums[i];
        if (i > 1) {
            take += dp[i - 2];
        }
        int nonTake = 0 + dp[i - 1];
        
        dp[i] = max(take, nonTake);
    }
    
    return dp[n - 1];
}

• Time Complexity: $O(N)$
• Space Complexity: $O(N)$ (storing an entire table).

6. Space Optimization: Eliminating the DP Array

When evaluating any index $i$ in our tabulation loop, we only ever inspect the previous two states: dp[i - 1] and dp[i - 2]. We never need access to dp[i - 3], dp[i - 4], or earlier indices.

The Rolling Variable Strategy

We can discard the full array and track just two variables:

• prev: Represents dp[i - 1]
• prev2: Represents dp[i - 2]
• curr_i: Computed value for the current index.

As the loop advances:

1. prev2 shifts to take the value of prev.
2. prev shifts to take the value of curr_i.

7. Complete Space-Optimized Code Walkthrough

Here is the ultimate, production-grade, space-optimized solution implementing $O(1)$ auxiliary space complexity:

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        
        int prev = nums[0]; // Represents dp[i-1]
        int prev2 = 0;      // Represents dp[i-2] (equivalent to 0 for index < 0)
        
        for (int i = 1; i < n; i++) {
            // Option 1: Take current element + best sum from 2 steps back
            int take = nums[i];
            if (i > 1) {
                take += prev2;
            }
            
            // Option 2: Skip current element, take best sum from 1 step back
            int nonTake = 0 + prev;
            
            // Current maximum sum
            int curr_i = max(take, nonTake);
            
            // Shift pointers forward for the next iteration
            prev2 = prev;
            prev = curr_i;
        }
        
        // 'prev' holds the final answer for dp[n-1]
        return prev;
    }
};

8. Summary and Key Takeaways

• Subsequence Constraints: When asked to find subsequences with adjacency constraints (e.g., house robber), always evaluate a Pick / Non-Pick framework.
• Index Shifting: Picking an element requires jumping to index - 2 to satisfy the non-adjacent rule, whereas skipping permits moving to index - 1.
• Overlapping Subproblems: Recursion trees naturally exhibit overlapping calculations, which makes both Memoization and Tabulation essential performance upgrades.
• Space Optimization Principle: Because state transitions only look back two steps (i-1 and i-2), the space complexity can be cleanly compressed from $O(N)$ down to $O(1)$ using rolling scalar variables (prev and prev2).
• Complexity Matrix: