← Recursion & DP

Micro-Drill #164 — House Robber II (circular)

Recursion & DP Target: 15s

Circular constraint: first and last are adjacent. Solve twice: once excluding first, once excluding last.

def rob(nums):
    if len(nums) == 1: return nums[0]
    def rob_linear(arr):
        prev2, prev1 = 0, 0
        for x in arr:
            prev2, prev1 = prev1, max(prev1, prev2 + x)
        return prev1
    return max(rob_linear(nums[1:]),   # skip first
               rob_linear(nums[:-1]))  # skip last

Type it from memory. Go.

Practice Problems

• 213. House Robber II
• 337. House Robber III

Related Coding Drills

• Drill #64 — House robber Medium
• Drill #147 — Jump Game II Medium
• Drill #61 — Meeting rooms II Medium