Learning Journal

3/1/2024

House Robber

Tags: algorithms leetcode dynamic_programming

function rob(nums: number[]): number {
   const arr:number[] = [];
   
   for(let i = 0; i < nums.length; i++){
       if(i === 0) arr.push(nums[i]);
       else if(i === 1) arr.push(Math.max(nums[0], nums[1]))
       else arr.push(Math.max(nums[i] + arr[i -2], arr[i -1]));
   }

   return arr[arr.length - 1];
};function rob(nums: number[]): number {
   const arr:number[] = [];
   
   for(let i = 0; i < nums.length; i++){
       if(i === 0) arr.push(nums[i]);
       else if(i === 1) arr.push(Math.max(nums[0], nums[1]))
       else arr.push(Math.max(nums[i] + arr[i -2], arr[i -1]));
   }

   return arr[arr.length - 1];
};

THE PROBLEM

This is the solution using a dynamic programming approach for this problem.

We can use the backtracking approach to solve this problem by recursion. Basically, you consider all case scenarios using a for loop to consider all indices as a starting point then inside the recursion function, you continue to use a for loop to consider all indices starting from 2 position to the right of the current index as the next starting point. The problem with this approach is the time and space complexity is too big.

So, we can use dynamic programming.

In my solution, I build an array in which the value at any index is the maximum value the thief can rob if the original array ends there. So, at index 1, the thief can only rob the first house, so the maximum value the thief can rob if the original array stops at index 1 is the value of the first house. At index 2, the thief can either rob the first or the second house, so the maximum value the thief can rob if the original array stops at index 2 is the maximum value of the first and second house. From this point on, the maximum value the thief can rob if the original array stops at index i is the maximum value that he or she can rob if the original array stops at index i-1 or the value at the current house plus the maximum value that he or she can rob if the original array stops at index i-2.

After the array that we are building has equal length to the original array, we stop and return its last value.

Revised by ChatGPT

This solution employs a dynamic programming approach to solve the "House Robber" problem.

Initially, one might consider a backtracking approach using recursion to explore all possible scenarios. This would involve using a loop to select each index as a starting point and then recursively choosing every index that is two positions to the right as the next starting point. However, this approach suffers from high time and space complexity.

To optimize, we use dynamic programming. The idea is to construct an array where each element represents the maximum amount of money the thief can rob up to that house. For example:

At the first house (index 0), the maximum is simply the value of that house.
At the second house (index 1), the maximum is the greater of the first two houses.
For subsequent houses (index i), the maximum is either the value of robbing the current house plus the maximum from two houses before (index i+2) or the maximum from the previous house (index i-1).

This logic ensures that we are not violating the rule of not robbing adjacent houses. By iterating through the array and applying this rule, we build up the maximum amount that can be robbed up to each house.

Finally, the solution is the last element of this array, which represents the maximum amount that can be robbed from the entire row of houses.