House Robber: A Dynamic Programming Solution

The "House Robber" problem is a fundamental question in dynamic programming. It challenges us to find the maximum amount of money a robber can steal from a row of houses without robbing two adjacent houses, as this would alert the police.

Problem Statement

Given an array of integers representing the amount of money in each house, determine the maximum amount of money you can rob without robbing two adjacent houses.

Example

• Input: nums = [1, 2, 3, 1] Output: 4 Explanation: Rob the first house (1) and the third house (3), totaling 4.

• Input: nums = [2, 7, 9, 3, 1] Output: 12 Explanation: Rob the first house (2), the third house (9), and the fifth house (1), totaling 12.

Dynamic Programming Solution

function rob(nums) {
  if (nums.length === 0) return 0;
  if (nums.length === 1) return nums[0];

  let dp = [nums[0], Math.max(nums[0], nums[1])];

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

  return dp[nums.length - 1];
}

Breaking Down the Solution

• Base Cases: Handle the cases where there are no houses or only one house.
• Initialize dp Array: Create a dp array to store the maximum amount of money that can be robbed up to each house.
• Dynamic Programming Iteration: Iterate through the array. For each house, calculate the maximum money by either robbing this house and the best house before the previous one, or by not robbing this house and taking the best total from the previous house.
• Return the Maximum Robbery Amount: The last element in the dp array represents the maximum amount of money that can be robbed.

Conclusion

The House Robber problem demonstrates the effectiveness of dynamic programming in solving optimization problems. It shows how to make decisions at each step to maximize the overall outcome while adhering to certain constraints.