Solving One-Dimensional Take-or-Skip Optimization

Welcome to the next lesson in our dynamic programming module. In our previous sessions, you've learned the fundamental mechanics of DP: identifying overlapping subproblems, using memoization to optimize recursion, converting that to bottom-up tabulation, and finally, optimizing space when dependencies allow.

Today, we'll put all those pieces together to tackle a classic and highly common interview pattern. Your learning outcome is to solve a one-dimensional take-or-skip optimization problem. These problems involve iterating through a sequence (like an array) and making a binary choice at each step—either take the current item or skip it—to achieve an optimal overall result. We will use the famous "House Robber" problem as our main example to master this pattern.

The "Take-or-Skip" Pattern: House Robber

Imagine you are a robber casing a street of houses. Each house i contains a certain amount of money, given by an array nums[i]. There's a catch: adjacent houses have interconnected security systems. If you rob two adjacent houses, the police will be alerted. Your goal is to figure out the maximum amount of money you can steal without triggering any alarms.

This problem is a perfect example of the "take-or-skip" pattern. For each house, you must decide:

1. Take (Rob): You get the money from the current house, but you cannot have robbed the previous one.
2. Skip (Don't Rob): You forgo the money in the current house, leaving you free to have robbed the previous one.

A brute-force approach would be to try every possible combination of robbing and skipping, which would involve exploring a decision tree of choices.

As you can see, this brute-force recursion is inefficient, with a time complexity of $O(2^n)$. The repeated subproblems signal that we can do much better with DP.

Developing the DP Recurrence

Let's apply the structured thinking of dynamic programming.

First, we need to define the state. A natural choice is to define dp[i] as the maximum amount of money that can be robbed considering houses from the beginning up to and including house i.

Next, we establish the transition, or recurrence relation. To calculate dp[i], we refer to our "take-or-skip" choice for house i:

• If we skip house i, we don't get nums[i]. The maximum amount we can have is whatever we accumulated up to the previous house, which is dp[i-1].
• If we take (rob) house i, we get nums[i]. Since we can't rob house i-1, the maximum amount we could have accumulated before this is the total from two houses ago, dp[i-2]. So, this choice yields nums[i] + dp[i-2].

Since we want to maximize our loot, dp[i] must be the best of these two options. This gives us our transition:

$$dp[i]=\max (dp[i-1],\text{nums}[i]+dp[i-2])$$

Finally, we need our base cases to start the process:

• dp[0]: For the first house, we can only rob it. So, dp[0] = nums[0].
• dp[1]: For the second house, we can either rob house 0 or house 1, but not both. So, dp[1] = \max(nums[0], nums[1]).

With the state, transition, and base cases defined, we can build our solution.

From Intuition to Tabulation

The video below by Greg Hogg provides an excellent, intuitive walkthrough of building the bottom-up DP solution. He visualizes how the dp array is filled step-by-step using the recurrence we just derived.

For a clear, written explanation in JavaScript, the following article is a great supplement.

Here is a TypeScript implementation of the tabulated solution. Notice how it directly maps to the base cases and transition formula.

function robTabulated(nums: number[]): number {
    const n = nums.length;
    if (n === 0) return 0;
    if (n === 1) return nums[0];

    // dp[i] = max money from houses 0..i
    const dp = new Array(n).fill(0);

    // Base cases
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1]);

    // Fill the rest of the table using the transition
    for (let i = 2; i < n; i++) {
        const robCurrent = nums[i] + dp[i - 2];
        const skipCurrent = dp[i - 1];
        dp[i] = Math.max(robCurrent, skipCurrent);
    }

    return dp[n - 1];
}

Space Optimization: A Familiar Pattern

Take another look at our transition: dp[i] = max(dp[i-1], nums[i] + dp[i-2]).

Does this look familiar? To compute the current state dp[i], we only need the two immediately preceding states, dp[i-1] and dp[i-2]. This is the exact same dependency we saw with the Fibonacci sequence in our last lesson!

This means we can apply the same space optimization technique, reducing our space complexity from O(n) for the dp array down to O(1) by using just a couple of variables to track the last two results.

The Greg Hogg video and the "Mastering Javascript" article both cover this optimization beautifully.

Here's the space-optimized solution in TypeScript. Let's use robTwoBack for the result from two steps ago (dp[i-2]) and robOneBack for the result from one step ago (dp[i-1]).

function robOptimized(nums: number[]): number {
    const n = nums.length;
    if (n === 0) return 0;
    if (n === 1) return nums[0];

    let robTwoBack = nums[0]; // Corresponds to dp[0]
    let robOneBack = Math.max(nums[0], nums[1]); // Corresponds to dp[1]

    for (let i = 2; i < n; i++) {
        // Calculate the current max based on previous two
        const currentMax = Math.max(robOneBack, nums[i] + robTwoBack);
        
        // Update variables for the next iteration
        robTwoBack = robOneBack;
        robOneBack = currentMax;
    }

    return robOneBack;
}

This final version has a time complexity of O(n) and a space complexity of O(1), which is an optimal solution for this problem and a strong demonstration of your DP skills in an interview.

Conclusion

You've now mastered a fundamental dynamic programming pattern. The "take-or-skip" structure appears in many problems, and recognizing it is the first step toward an efficient solution.

Here are your key takeaways:

• Pattern Recognition: Identify problems where you iterate through a sequence making a binary choice at each step (e.g., take/skip, use/don't use, buy/sell).
• State Definition: The DP state dp[i] is typically defined as the optimal value considering elements up to index i.
• Transition Formula: The core of the solution is the recurrence relation that formally expresses the "take-or-skip" choice, usually by comparing the outcome of each option.
• Optimization: For 1D DP, always check the dependencies. If dp[i] only depends on a fixed number of recent states (like dp[i-1] and dp[i-2]), you can optimize the space from O(n) to O(1).

In our next lesson, we will extend these ideas to two dimensions by tackling grid-based path-counting and minimum-cost problems. You'll see how the same principles of defining state, transitions, and base cases apply, just on a 2D dp table.