House robber (recursion)

Medium TimeO(2ⁿ) naive; O(n) memoised SpaceO(n) stack

A row of houses each hold some money, but robbing two next to each other sets off the alarm. Return the most that can be taken. The row does not wrap around, so the first and last houses are not adjacent, and taking nothing is allowed, so the answer is never negative.

Examples

Example 1

Input
nums = [2, 7, 9, 3, 1]i = 0
Output
12
2 + 9 + 1 = 12; the richer-looking 7 + 3 comes to only 10.

Example 2

Input
nums = [5, 1, 1, 5]i = 0
Output
10
5 + 5 at the two ends, with both 1s between them skipped.

The Code

function rob(nums, i) {
  if (i >= nums.length) return 0;
  const robThis = nums[i] + rob(nums, i + 2);
  const skip = rob(nums, i + 1);
  return Math.max(robThis, skip);
}
rob([2, 7, 9, 3, 1], 0);
Done

The first 17 calls, of 25. This one does not fit on a page.

Step through rob([2, 7, 9, 3, 1], 0) call by call

More like this

All dynamic programming examples (20) →