House Robber

 You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

 

Example 1:

Input: nums = [1,2,3,1]

Output: 4

Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).

Total amount you can rob = 1 + 3 = 4.

Example 2:

Input: nums = [2,7,9,3,1]

Output: 12

Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).

Total amount you can rob = 2 + 9 + 1 = 12.

 

Constraints:

1 <= nums.length <= 100

0 <= nums[i] <= 400

🔁 Dry Run:

Input: nums = [2, 1, 4, 9]

1. rob() → calls solve(nums, 0, dp)

2. From index 0:

   • steal = 2 + solve(2)

   • skip = solve(1)

3. From index 2:

   • steal = 4 + solve(4) → out of bound → 0

   • skip = solve(3)

   • solve(3) = 9 + solve(5) = 9

   ⇒ dp[2] = max(4, 9) = 9

4. Back to index 0:

   • steal = 2 + 9 = 11

   • skip = solve(1)

     • steal = 1 + solve(3) → already 9

     • skip = solve(2) → already 9

     • ⇒ dp[1] = max(10, 9) = 10

5. Final: max(11, 10) = ✅ 11

---

🧠 Memoization Advantage

It avoids repeating work:

• Without memo: solve(3) called 2–3 times.

• With memo: Called once → reused.

class Solution {

    public int rob(int[] nums) {

        int n = nums.length;

        int[] dp = new int[n];          // Step 1: Create dp array

        Arrays.fill(dp, -1);            // Step 2: Fill with -1 (means not yet computed)

        return solve(nums, 0, dp);      // Step 3: Start from index 0

    }

    private int solve(int[] nums, int i, int[] dp) {

        if (i >= nums.length) return 0; // Step 4: Base case - beyond array

        if (dp[i] != -1) return dp[i];  // Step 5: If already solved, return it

        int steal = nums[i] + solve(nums, i + 2, dp); // Step 6: Rob this house and go to i+2

        int skip = solve(nums, i + 1, dp);            // Step 7: Skip this house, go to i+1

        dp[i] = Math.max(steal, skip);  // Step 8: Store max in dp[i]

        return dp[i];                   // Step 9: Return answer

    }

}