Q41: House Robber (Dynamic Programming)

Find the maximum money you can rob tonight without alerting police (cannot rob adjacent houses).

DP House Robber O(1) Space

function rob(nums) {
  let rob1 = 0;
  let rob2 = 0;
  
  for (let n of nums) {
    let temp = Math.max(n + rob1, rob2);
    rob1 = rob2;
    rob2 = temp;
  }
  return rob2;
}

console.log(rob([1, 2, 3, 1])); // 4 (Rob house 1 and 3)

💡 At house n, compares robbing current house plus max from two houses prior (n + rob1) against max from previous house (rob2). Shifts window values forward.

Key Takeaways

State transition: $dp[i] = \max(dp[i-1], dp[i-2] + \text{nums}[i])$.
Optimizable to O(1) space tracking two previous max values (rob1, rob2).

Knowledge Check

What constraint prevents taking the simple sum of all array elements in House Robber?

Q41: House Robber (Dynamic Programming)

STAY UPDATED WITH BYTES!