Q17: How do you solve the House Robber problem using Dynamic Programming?
Robbing adjacent houses triggers security alarms. At each house $i$, choose maximum of:
- Rob house $i$:
nums[i] + rob(i - 2) - Skip house $i$:
rob(i - 1)Recurrence: $dp[i] = max(nums[i] + dp[i-2], dp[i-1])$.
House Robber DP Solution
public class HouseRobber {
public static int rob(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int prev2 = 0, prev1 = 0;
for (int num : nums) {
int temp = Math.max(num + prev2, prev1);
prev2 = prev1;
prev1 = temp;
}
return prev1;
}
}💡 Tracks optimal loot values while skipping adjacent houses.
Key Takeaways
- Recurrence relation: $dp[i] = max(nums[i] + dp[i-2], dp[i-1])$.
- Optimize memory to $O(1)$ space using two variables.
Knowledge Check
If houses are arranged in a CIRCLE (House Robber II), how do you adapt the solution?