House Robber
Medium1-D dynamic programming
Houses stand in a row, and nums[i] is the cash kept in house i. A thief can take the cash from any houses he likes, except that he can never take from two houses that stand next to each other: that sets off the alarm.
Return the most cash he can take.
Examples
Input: nums = [3, 10, 4, 2, 9] Output: 19
Take 10 and 9. Taking every other house (3 + 4 + 9) gives only 16.
Input: nums = [6, 1, 1, 6] Output: 12
Take the first and the last house, with two houses skipped between them.
Constraints
1 ≤ nums.length ≤ 1000 ≤ nums[i] ≤ 400
Stuck?
Hint 1
At house i there are two choices: skip it and keep the best total up to house i - 1, or take it and add it to the best total up to house i - 2.
Hint 2
You only ever look two houses back, so keep two running totals and slide them along the row.
The idea
At each house the thief either skips it or takes it. Skipping keeps the best total up to the house before; taking adds its cash to the best total up to two houses back, which leaves its neighbour alone. So the best total at any house depends only on the two totals behind it.
Time O(n)Extra space O(1)
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 4
oneBack is the best total up to the house behind the current one, and twoBack the best up to the house before that. Before the first house nothing has been taken, so both are 0.
function rob(nums) { let twoBack = 0; let oneBack = 0; for (const cash of nums) { const best = Math.max(oneBack, twoBack + cash); twoBack = oneBack; oneBack = best; } return oneBack;}The trap
Adding up the even houses and the odd houses and taking the larger sum never robs two neighbours, so it looks safe, and it is right on many rows. But the best plan can skip two or more houses in a row, such as taking only the first and the last of four. Alternating picks never leave a gap that wide, so any row whose best plan needs one comes out short.
function rob(nums) { let even = 0; let odd = 0; nums.forEach((cash, i) => { if (i % 2 === 0) even += cash; else odd += cash; }); return Math.max(even, odd); // only ever tries every other house}