9.7 House Robber (Non-Adjacent Choice)
চিনবেন কীভাবে
"can't pick two adjacent" — take or skip each element, with neighbours blocking each other; two states: taken / not taken
Demo · approach · কোড — আগে নিজে চেষ্টা, আটকালে খুলুন
Demo: House Robber — LC 198 (Medium — Amazon/Google High)
Statement (Demo): nums[i] is the money in house i. Without robbing two adjacent houses, return the most money you can rob in one night.
Example: nums=[1,2,3,1] → 4 (1 + 3) | ⚡ n ≤ 100
Approach: Two running values — robbed (rob this house: previous skipped + this money) and skipped (skip it: the better of the previous two).
function rob(nums) {
let robbed = 0,
skipped = 0;
for (const x of nums)
[robbed, skipped] = [skipped + x, Math.max(robbed, skipped)];
return Math.max(robbed, skipped);
}
Complexity: Time O(n), Space O(1)
Demo · House Robberplan · দিন ০৪৬LC 198
নোট · ফাঁকা
প্রবলেম
- House Robber IIILC 337(tree DP — every node returns a [rob, skip] pair)
Statement: The houses form a binary tree. Robbing two directly linked houses (parent and child) on the same night is not allowed. Return the most money you can rob.
Example:root=[3,2,3,null,3,null,1]→7(3 + 3 + 1) | ⚡ nodes≤ 10⁴নোট · ফাঁকা