LeetCode: House Robber Solution

Approach

Let f(i) be the maximum amount robbeb starting from house i

At house i, there are two choices:

• Rob
• Skip

1f(i) = max(rob(i), skip(i))

Implementation

1var rob = function (nums) {
2  const memo = {}
3
4  const recursion = i => {
5    if (i >= nums.length) return 0
6
7    if (memo[i] != null) return memo[i]
8
9    const rob = nums[i] + recursion(i + 2)
10    const skip = recursion(i + 1)
11
12    return (memo[i] = Math.max(rob, skip))
13  }
14
15  return recursion(0)
16}

References

Original problem

Similar problems

Maximum Product Subarray

House Robber II

Paint House

Paint Fence

House Robber III

Non-negative Integers without Consecutive Ones

Coin Path

Delete and Earn

Solving Questions With Brainpower

Count Number of Ways to Place Houses