House Robber: Four Steps to Solving Dynamic Programming Problems

Example problem for this lesson: LeetCode 198. House Robber (Easy)

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

Given an array of non-negative integers representing the amount of money in each house, determine the maximum amount of money you can rob without triggering the alarm.

Example:

Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (amount = 1), then rob house 3 (amount = 3).
     Maximum amount = 1 + 3 = 4.

The House Robber problem is a classic introductory dynamic programming problem. If you’re not yet familiar with dynamic programming or haven’t solved many DP problems before, I highly recommend using House Robber as your starting point.

Dynamic programming is often considered the hardest type of algorithm problem by many students, because the solutions are flexible and come in many variations. Yet DP frequently appears as the final, most challenging problem in coding tests, so we have no choice but to face it.

In truth, dynamic programming is a category where “learning by analogy” really pays off. Many DP solutions require you to have practiced a particular type of example problem, so that when you encounter a similar problem later, the right approach comes to mind. If you’ve solved quite a few problems but still feel lost when facing a new one, it means the problems you’ve practiced aren’t representative enough. For instance, the coin change problem that many articles love to elaborate on is actually not the best choice for understanding the core ideas of dynamic programming.

This is exactly why I write the “LeetCode Problem Deep Dives” series. My articles aim to do two things: first, choose the most representative example problems; second, use each example to teach the general approach for an entire class of problems. Starting from this lesson, I’ll cover dynamic programming across several articles, each using the most typical example problem to help you learn the DP problem-solving patterns.

In this article, I’ve chosen a very typical dynamic programming problem: House Robber. By walking through the solution step by step, I’ll explain the four fundamental steps for solving dynamic programming problems.

Four Steps to Solving Dynamic Programming Problems

The four steps for solving dynamic programming problems are:

• Define the subproblem
• Write out the recurrence relation for the subproblem
• Determine the computation order of the DP array
• Space optimization (optional)

To be honest, I’ve used these four steps to solve every single one of the dozens of dynamic programming problems I’ve tackled on LeetCode. This four-step approach applies to any dynamic programming problem and helps you quickly organize all the key points of a solution.

Step 1: Define the Subproblem

Anyone who has had even a little exposure to dynamic programming knows that DP involves a “subproblem” definition. What is a subproblem? A subproblem is a problem that is similar to the original problem but smaller in scale. For example, in the House Robber problem, the original problem is “the maximum amount that can be robbed from all houses.” If we reduce the scale, the subproblem becomes “the maximum amount that can be robbed from $k$ houses,” denoted as $f(k)$.

As you can see, the subproblem is parameterized — our subproblem definition includes a parameter $k$. If there are $n$ houses in total, then there are $n$ subproblems. Dynamic programming essentially solves the original problem by solving this collection of subproblems. This requires the subproblems to have two properties:

• The original problem can be expressed in terms of subproblems. For example, in this problem, when $k=n$, the subproblem is actually the original problem. Otherwise, if solving all the subproblems still doesn’t solve the original problem, what’s the point?
• The solution to one subproblem can be derived from the solutions to other subproblems. For example, in this problem, $f(k)$ can be derived from $f(k-1)$ and $f(k-2)$ — the specific reasoning will be explained later. This property is what textbooks call “optimal substructure.” If you can’t define such a subproblem, then the problem can’t actually be solved with dynamic programming.

Since the House Robber problem is relatively simple, defining the subproblem is quite intuitive. Some harder dynamic programming problems may require special techniques for defining subproblems.

Step 2: Write Out the Recurrence Relation

This step is the most critical part of solving a dynamic programming problem. However, it’s also the step that’s hardest to see in the code itself. When solving problems, it’s best to write down the reasoning for this step as comments. Don’t rush through DP problems — make sure every detail is correct. Otherwise, you’ll spend five minutes writing code and thirty minutes debugging. Not ideal, right?

Let’s analyze the recurrence relation for this problem:

Suppose there are $n$ houses in total, with amounts $H_0, H_1, \dots, H_{n-1}$ respectively. The subproblem $f(k)$ represents the maximum amount that can be robbed from the first $k$ houses (i.e., $H_0, H_1, \dots, H_{k-1}$). Then, there are two ways to rob $k$ houses:

The last house among the $k$ houses is $H_{k-1}$. If we don’t rob this house, the problem reduces to finding the maximum amount from the first $k-1$ houses, which is subproblem $f(k-1)$. If we do rob this house, then the previous house $H_{k-2}$ obviously can’t be robbed, while the other houses are unaffected. The problem then reduces to finding the maximum amount from the first $k-2$ houses. Between these two cases, we choose the one with the larger amount.

$$f(k) = \max \begin{cases} f(k-1) \\ f(k-2) + H_{k-1} \end{cases}$$

Additionally, when writing the recurrence relation, we need to pay attention to the base cases. This ensures a complete recurrence relation and makes it less likely to have boundary condition errors when coding. In this problem, the base cases are the subproblems for $k=0$ and $k=1$:

• When $k=0$, there are no houses, so $f(0) = 0$.
• When $k=1$, there is only one house — just rob it, so $f(1) = H_0$.

Step 3: Determine the Computation Order of the DP Array

After establishing the recurrence relation for the subproblems, the next step is to compute these subproblems one by one. Many tutorials mention that dynamic programming has two computation approaches: a top-down recursive method with memoization, and a bottom-up iterative method using a DP array. However, for typical dynamic programming problems, the iterative method works well in 99% of cases, so it’s best to stick with the bottom-up approach from the start, using a DP array. This is what helps you truly grasp the essence of dynamic programming.

The DP array can also be called the “subproblem array,” because each element in the DP array corresponds to a subproblem. As shown in the diagram below, dp[k] corresponds to subproblem $f(k)$, i.e., the maximum amount from robbing the first $k$ houses.

Then, once we figure out the computation order of the subproblems, we can determine the computation order of the DP array. For the House Robber problem, analyzing the dependency relationships between subproblems reveals that each $f(k)$ depends on $f(k-1)$ and $f(k-2)$. In other words, dp[k] depends on dp[k-1] and dp[k-2], as shown below.

Since all dependencies in the DP array point to the right, the computation order is from left to right. This way, we can ensure that when computing a subproblem, all the subproblems it depends on have already been computed.

With the computation order of the DP array determined, we can now write the solution code:

public int rob(int[] nums) {
    if (nums.length == 0) {
        return 0;
    }
    // Subproblem:
    // f(k) = max amount from robbing rooms [0..k)

    // f(0) = 0
    // f(1) = nums[0]
    // f(k) = max{ rob(k-1), nums[k-1] + rob(k-2) }

    int N = nums.length;
    int[] dp = new int[N+1];
    dp[0] = 0;
    dp[1] = nums[0];
    for (int k = 2; k <= N; k++) {
        // Apply the subproblem recurrence relation
        dp[k] = Math.max(dp[k-1], nums[k-1] + dp[k-2]);
    }
    return dp[N];
}

Notice that the code above includes a large block of comments about the subproblem definition and recurrence relation. In an interview setting, we generally need to explain the subproblem definition and recurrence relation to the interviewer first, and write these down as comments along the way. This serves two purposes: it helps you avoid mistakes while coding, and it helps the interviewer better understand your thought process.

Step 4: Space Optimization

Space optimization is an advanced topic in dynamic programming. For beginners, you can skip this part — the only downside is slightly higher space complexity. That said, the House Robber problem serves as an excellent example of space optimization, so it’s worth learning about.

Let’s revisit the method for computing the Fibonacci sequence that we learned during our introduction to programming. The recurrence relation for the Fibonacci sequence is $f(n) = f(n-1) + f(n-2)$. Doesn’t this look exactly like the House Robber problem? When computing the Fibonacci sequence, we only need three variables — no DP array required:

// Compute Fibonacci sequence
// f(1) = f(2) = 1, f(n) = f(n-1) + f(n-2)
int fib(int n) {
    if (n <= 2) {
        return 1;
    }
    int a = 1;
    int b = 1;
    for (int i = 2; i < n; i++) {
        int c = a + b;
        a = b;
        b = c;
    }
    return b;
}

Remember this code. This code, which we learned very early on, actually contains the space optimization technique for House Robber-type dynamic programming problems.

The basic principle of space optimization is that in many cases, we don’t need to keep the entire DP array at all times. For the House Robber problem, we notice that when computing the final step $f(n)$, we only use the results of $f(n-1)$ and $f(n-2)$. The subproblems before $n-3$ are effectively no longer needed.

So we can use just two variables to store the results of two subproblems and compute all subproblems in sequence. This reduces the space complexity from $O(n)$ to $O(1)$. The animation below compares the approach before and after space optimization:

The optimized code is shown below:

public int rob(int[] nums) {
    int prev = 0;
    int curr = 0;

    // Each iteration computes "max amount robbed up to the current house"
    for (int i : nums) {
        // At the start of the loop, curr represents dp[k-1], prev represents dp[k-2]
        // dp[k] = max{ dp[k-1], dp[k-2] + i }
        int temp = Math.max(curr, prev + i);
        prev = curr;
        curr = temp;
        // At the end of the loop, curr represents dp[k], prev represents dp[k-1]
    }

    return curr;
}

As you can see, we only use three variables: prev, curr, and temp. In each iteration, prev represents dp[k-2], curr represents dp[k-1], and temp is responsible for computing the value of dp[k], which then gets shifted forward in the next iteration. The way these three variables operate is exactly the same as the three variables in the Fibonacci sequence computation.

If you’re a Python enthusiast, you can take advantage of multiple assignment syntax to eliminate the temp variable, reducing the loop body to a single line:

def rob(self, nums: List[int]) -> int:
    prev = 0
    curr = 0
    
    # Each iteration computes "max amount robbed up to the current house"
    for i in nums:
        # At the start of the loop, curr represents dp[k-1], prev represents dp[k-2]
        # dp[k] = max{ dp[k-1], dp[k-2] + i }
        prev, curr = curr, max(curr, prev + i)
        # At the end of the loop, curr represents dp[k], prev represents dp[k-1]

    return curr

Summary

This article used the House Robber problem to demonstrate the four fundamental steps for solving dynamic programming problems. There are many types of dynamic programming problems, and some can be quite challenging. But no matter how much they vary, they all revolve around these four basic steps — the difference is simply that certain steps become harder. For example:

• In the “define the subproblem” step, some problems require defining two-dimensional or three-dimensional subproblems.
• In the “subproblem recurrence relation” step, some problems require case-by-case analysis with complex max, min, or sum expressions.
• In the “DP array computation order” step, some problems require reverse computation or even diagonal computation.
• In the “space optimization” step, some problems require temporary variables or special computation orders.

You might ask: with so many variations, how can I possibly learn them all? The answer is to progress from easy to hard, step by step — thoroughly understand the example problems, and learn by analogy.

If you’ve made it this far, congratulations on taking the first step into dynamic programming. In the upcoming articles, I’ll progressively cover other dynamic programming problems, helping you gradually master the techniques for DP problems. Stay tuned.