Q42: House Robber II (Circular DP)
All houses are arranged in a circle. Find max stolen money given adjacent houses cannot be robbed.
Circular House Robber Solution
function rob(nums) {
if (nums.length === 1) return nums[0];
function robLinear(arr) {
let rob1 = 0, rob2 = 0;
for (let n of arr) {
let temp = Math.max(n + rob1, rob2);
rob1 = rob2;
rob2 = temp;
}
return rob2;
}
const case1 = robLinear(nums.slice(0, nums.length - 1));
const case2 = robLinear(nums.slice(1));
return Math.max(case1, case2);
}
console.log(rob([2, 3, 2])); // 3💡 Splits problem into two linear sub-problems: excluding the last house (
0..n-2) vs excluding the first house (1..n-1), returning whichever yield is higher.Key Takeaways
- Circular arrangement implies first house and last house are adjacent and cannot both be robbed.
- Run standard House Robber algorithm twice: range
0..n-2and range1..n-1, taking maximum result.
Knowledge Check
How does House Robber II handle the circular house arrangement constraint?