🗓️ Day 19: House Robber Pattern

📘 What You’ll Learn

• What is the House Robber pattern?
• Why you can't rob adjacent houses
• Applying dynamic programming to maximize profit
• Translating logic into TypeScript
• Recursion → Memoization → Tabulation
• Real LeetCode example

🧠 Concept

The House Robber pattern is a classic dynamic programming scenario. You’re given an array of non-negative integers representing the amount of money in each house. You cannot rob two adjacent houses, or you’ll trigger the alarm! 🚨💸

Your goal is to pick houses to rob such that the sum of stolen money is maximized, without robbing adjacent houses.

Think: Should I rob this house and skip the next, or skip this one and check the next house's opportunity? 🤔

📊 Visualization

Let's say we have houses with money:

Index:   0   1   2   3   4
Money:  2   7   9   3   1

You can't rob house 1 and 2 together, or 2 and 3. So you calculate max loot at each step:

dp[i] = max(dp[i-1], dp[i-2] + nums[i])

💻 TypeScript Examples

❌ Recursive Brute-force

function rob(nums: number[]): number {
  function helper(i: number): number {
    if (i >= nums.length) return 0;
    return Math.max(
      helper(i + 1),              // skip this house
      nums[i] + helper(i + 2)     // rob this house
    );
  }
  return helper(0);
}

• ⏱️ Time: O(2ⁿ) — too slow!

✅ Top-Down Memoization

function rob(nums: number[]): number {
  const memo: Record<number, number> = {};
  function dp(i: number): number {
    if (i >= nums.length) return 0;
    if (i in memo) return memo[i];
    memo[i] = Math.max(dp(i + 1), nums[i] + dp(i + 2));
    return memo[i];
  }
  return dp(0);
}

• ⏱️ Time: O(n)
• 💾 Space: O(n) (call stack + memo)

✅ Bottom-Up Tabulation

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

• ⏱️ Time: O(n)
• 💾 Space: O(n)

💡 Optimized DP (Constant Space)

function rob(nums: number[]): number {
  let prev1 = 0, prev2 = 0;
  for (let num of nums) {
    let temp = Math.max(prev1, prev2 + num);
    prev2 = prev1;
    prev1 = temp;
  }
  return prev1;
}

• ⏱️ Time: O(n)
• 💾 Space: O(1) 🚀

🧪 LeetCode Homework

📘 198. House Robber

🧩 You are a professional robber. Each house has a certain amount of money. Adjacent houses have security systems connected — robbing two in a row triggers an alarm. Return the maximum amount you can rob.

function rob(nums: number[]): number {
  let prev1 = 0, prev2 = 0;
  for (let num of nums) {
    let temp = Math.max(prev1, prev2 + num);
    prev2 = prev1;
    prev1 = temp;
  }
  return prev1;
}

const houses = [2,7,9,3,1];
console.log(rob(houses)); // 12

📌 Key Takeaways

• Robbing adjacent houses = 🚨
• Use DP to track max amount without violating rules
• Learn to convert recursive → memoization → tabulation → optimized
• This pattern appears in more advanced problems (e.g., circular houses, trees)

🔮 Up Next

▶️ Day 20: House Robber II (Circular Houses)