1-D Dynamic Programming Take it or skip it
517. House Robber II
Houses stand in a circle, and nums[i] is the amount of money in house i. Because they form a circle, the
last house is next to the first one.
Neighbouring houses share an alarm, so the robber never robs two houses that are next to each other. That includes the first and the last house. Any other choice of houses is allowed, including robbing none.
Return the most money the robber can take.
Example 1
Input: nums = [6, 1, 3, 8, 2, 5]
14Explanation: In a row, 6 + 8 + 5 = 19 would be best, but houses 0 and 5 are neighbours here. The best allowed choices are 6 + 8 and 1 + 8 + 5, both 14.
Example 2
Input: nums = [9]
9Explanation: One house has no neighbour, so the robber takes it.
Example 3
Input: nums = [1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000]
3000000000Explanation: Seven houses in a circle allow at most three robbed houses, such as houses 0, 2 and 4. Houses 0, 2, 4 and 6 would break the rule, because houses 6 and 0 are neighbours.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ nums.length ≤ 1050 ≤ nums[i] ≤ 109
Clarifying questions
What you would ask an interviewer before writing any code.