770. House Robber (Recursive + Memoization)

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed; however, adjacent houses have connected alarms, and robbing two adjacent houses on the same night will trigger the alarm. Given an integer array nums representing the amount of money at each house, return the MAXIMUM amount of money you can rob tonight without triggering any alarm. Implement with recursion + memoization.

Input: An integer array nums with nums[i] >= 0.

Output: Return an integer: the maximum total robbable amount.

Examples

Input: [1,2,3,1]
Output: 4
Explanation: Rob houses 0 and 2: 1 + 3 = 4.

Input: [2,7,9,3,1]
Output: 12
Explanation: Rob houses 0, 2, 4: 2 + 9 + 1 = 12.

Input: [2,1,1,2]
Output: 4
Explanation: Rob houses 0 and 3: 2 + 2 = 4.

Constraints

• 1 <= nums.length <= 200
• 0 <= nums[i] <= 10^9

Asked by