House Thief Problem

There are n houses built in a line, each containing some value. A thief is going to steal the maximum value from these houses. However, he can’t steal in 2 adjacent houses. What is the maximum stolen value?

Example 1
-----------
n: [6, 7, 1, 30, 8, 2, 4]
max value: 41
Explanation: Thief will steal from houses with 7, 30, 4.

Example 2
-----------
n: [20, 5, 1, 13, 6, 11, 40]
max value: 73
Explanation: Thief will steal from houses with 20, 13, 40.

Solution

This problem can be solved by applying Divide and Conquer to break down the problem into smaller subproblems. Thus, by solving this subproblems, we will arrive at our final answer. Let’s look at Example 1 and try to derive the subproblems.

f(7 houses) = max of [6 + f(remaining 5 houses)] or [0 + f(6 remaining 6 houses)]

So, what the above subproblems are saying is that, since we can’t steal from two adjacent houses, the thief can either steal from the first house, and then skip the second house and move on to the other remaining 5 houses given that we have 7 houses in total. Hence 6 + f(remaining 5 houses). Or, the thief can skip the first house and steal from the remaining 6 houses, and hence, 0 + f(remaining 6 houses). We’re looking for the maximum value which the thief can steal. Therefore, we want to find the maximum value returned from the two subproblems.

Code Algortihm

function stealMoney(n: number[], i: number): number {
  if (i >= n.length) return 0;

  const money1 = n[i] + stealMoney(n, i + 2);
  const money2 = stealMoney(n, i + 1);

  return Math.max(money1, money2);
}

Optimisation

Let’s look at the an example of the recursion tree to examine whether we need to optimise it.

                                                        stealMoney(0)
                                                      /                 \
                                                  /                         \
                                              /                                 \
                                          /                                         \
                                      /                                                 \
                                stealMoney(2)                                        stealMoney(1)
                        /                           \                                 /             \
                stealMoney(4)                  stealMoney(3)                   stealMoney(3)   stealMoney(2)
                /             \                 /           \                    /            \
          stealMoney(6)  stealMoney(5)  stealMoney(5)  stealMoney(4)   stealMoney(5)   stealMoney(4)
        /             \
stealMoney(8)    stealMoney(7)

We can see from the above recursion tree that stealMoney(3), stealMoney(4) and stealMoney(5) have been computed multiple times. Hence, we can apply Dynamic Programming to optimise this solution.

Top Down Approach

We will start off by applying Top Down Approach (also known as Memoization).

type HashTable = {
  [x: number]: number;
};

const dp: HashTable = {};

function stealMoney(n: number[], i: number): number {
  if (i >= n.length) return 0;

  if (!(i in dp)) {
    const money1 = n[i] + stealMoney(n, i + 2);
    const money2 = stealMoney(n, i + 1);
    dp[i] = Math.max(money1, money2);
  }

  return dp[i];
}

Bottom Up Approach

We can now then apply some reverse engineer to use the Bottom Up Approach (also known as Tabulation). Let’s visualise how dp is filled using Top Down Approach.

We can then now reverse the process. Let’s visualize how Bottom Up Approach works here.

type HashTable = {
  [x: number]: number;
};

function stealMoney(n: number[]): number {
  const dp: HashTable = {};

  for (let i = n.length + 1; i > -1; --i) {
    if (i > n.length - 1) {
      dp[i] = 0;
    } else {
      dp[i] = Math.max(n[i] + dp[i + 2], dp[i + 1]);
    }
  }

  return dp[0];
}