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/
