House Robber: From recursion to memoization and ultimately space-optimized solution

One of the most popular dynamic programming problems is the famous house robber. If we narrow down the category, it is the pick or not pick problem. Based on the basics of house robber problem, a few more problems are available are out there by adding more layers of complexity.

Today, we will get the most basic problem and solve it step by step. We will start by using the recursion and later on top of the recursion problem, we will use the tabulation of dynamic programming. Finally, we will optimize the space.

The house robber problem is explained, as follows,

There are a few houses in a row and as a robber, I can not rob adjacent houses. This implies, if I rob house 1, I can not rob house 2. After house 1, I have to choose house 3 or 4 or so on. However, If I do not rob house 1, then I may rob house 2.

With this in our mind, the simplest solution is, to write a recursion and try all the possibilities.

Recursion

Recursion will be the brute force solution, where we will explore all the possibilities and figure out the maximum value. We can consider any of the sequences, from the first to the last index or vice-versa of the array. Here’s a solution, driving from the first to the last index.

function rob(nums: number[]): number {
    const helper = (index) => {
        if (index >= nums.length) {
            return 0;
        }

        const pick = nums[index] + helper(index + 2);
        const notPick = helper(index + 1);

        return Math.max(pick, notPick);
    }

    return helper(0);
};

DP Memoization

Now, we can see the sub-problems, where, we may calculate the index multiple times using the function. Instead, to persist the already calculated value, we can consider an array dp of the array size.

function rob(nums: number[]): number {
    const dp = new Array(nums.length).fill(-1);
    const helper = (index) => {
        if (index >= nums.length) {
            return 0;
        }

        if (dp[index] !== -1) {
            return dp[index];
        }

        const pick = nums[index] + helper(index + 2);
        const notPick = helper(index + 1);

        dp[index] = Math.max(pick, notPick);
        return dp[index];
    }
    return helper(0);
};

Now, if we already calculated the value, we skip the further calculation and get the calculated from the array.

We can calculate the the value from last to the first index as well as follows,

function rob(nums: number[]): number {
    const dp = new Array(nums.length).fill(-1);
    const helper = (index) => {
        if (index === 0) {
            return nums[index];
        }

        if (index < 0) {
            return 0;
        }

        if (dp[index] !== -1) {
            return dp[index];
        } 

        const pick = nums[index] + helper(index - 2);
        const notPick = helper(index - 1);
        dp[index] = Math.max(pick, notPick);

        return dp[index];
    }

    return helper(nums.length - 1);
};

Tabulation

If we observe closely, we can see, the base value of the recursion,

• If there is only one house, the result is the first house's value

• For the first two houses, the result is the maximum of the first two houses, since we can not take these consecutive two houses

• For the rest of the houses, if we pick the house, just can not pick the immediate previous one

Considering these, can calculate the final maximum results as below,

function rob(nums: number[]): number {
    const dp = new Array(nums.length).fill(0);
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1]);

    for (let i = 2; i < nums.length; i += 1) {
        const take = nums[i] + dp[i - 2];
        const notTake = dp[i - 1];
        dp[i] = Math.max(take, notTake);
    }

    return dp[nums.length - 1];
};

Space Optimization

From the last solution, it occurs, that the solution of the current index only depends on the previous two values. With this consideration, we can simply avoid the entire O(n) array with a just two variables,

function rob(nums: number[]): number {
    let rob1 = 0;
    let rob2 = 0;

    for (let i = 0; i < nums.length; i += 1) {
        const take = rob1 + nums[i];
        const notTake = rob2;
        rob1 = rob2
        rob2 = Math.max(take, notTake)
    }

    return rob2;
};

This is the most optimized solution with constant space and O(n) runtime complexity.

For practice: https://leetcode.com/problems/house-robber/