LeetCode: 213. House Robber II

Summary

Given an integer array nums representing the amount of money in each house, return the maximum amount of money you can rob tonight without alerting the police.

Condition: All houses in this place are arranged in a circle. Adjacent houses are connected to the same security system, and it automatically contacts the police if two adjacent houses are broken into on the same night.

Approach

The basic approach is dynamic programming. We can calculate the maximum amount we can rob up to the i-th house:

max_stash[i] = max(max_stash[i - 2] + nums[i], max_stash[i - 1])

However, we cannot rob the first and last houses at the same time because they are adjacent.

We check two cases:

Rob houses from 0 to n - 2
Rob houses from 1 to n - 1

Then return the maximum of those two results.

Function

Function dp(start, end): n = len(nums) If end < start or start > n - 1: return 0 If start == end: return nums[start] size = end - start + 1 dp = [0] * (size + 2) For i in start..end: dp[i - start + 2] = max(dp[i - start] + nums[i], dp[i - start + 1]) return dp[-1]

Main: return max(dp(0, n - 2), dp(1, n - 1))

If the length is 0, start = 0 and end = -1, so it returns 0. If the length is 1, start = 0 and end = 0, so it returns nums[0]. The second call, dp(1, 0), returns 0 because end < start. If the length is 2, the result is max(nums[0], nums[1]).

Complexity

Time Complexity: O(N), where N is the number of houses. Space Complexity: O(N).