1-D Dynamic Programming Take it or skip it
516. House Robber
Houses stand in a row along a street, and nums[i] is the amount of money in house i. A robber wants to
take as much money as possible in one night.
The houses next to each other share an alarm. If two neighbouring houses are both robbed, the alarm goes off, so the robber never robs two houses that are next to each other. Any other choice of houses is allowed, including robbing none.
Return the most money the robber can take.
Example 1
Input: nums = [5, 1, 2, 9, 4]
14Explanation: Rob houses 0 and 3 for 5 + 9 = 14. Robbing every other house gives 5 + 2 + 4 = 11 or 1 + 9 = 10.
Example 2
Input: nums = [4, 0, 0, 4]
8Explanation: Rob the first and the last house. Two houses in a row may be skipped.
Example 3
Input: nums = [1000000000, 1, 1000000000, 1, 1000000000]
3000000000Explanation: Rob houses 0, 2 and 4.
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.