You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. The only constraint is that adjacent houses have security systems connected — you cannot rob two adjacent houses.
Given an integer array nums, return the maximum amount of money you can rob tonight.
Example 1
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (1) and house 3 (3).
Example 2
Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1, 3, 5: 2+9+1=12.
1 <= nums.length <= 1000 <= nums[i] <= 400The brute-force recursive idea: at each house, either rob it (skip the next one) or don't (move to the next one) — try both branches and take the best.
dp[i] = the maximum money robbable considering houses 0..i — built from dp[i-1] (skip house i) and dp[i-2] + nums[i] (rob house i).
Since dp[i] only ever depends on the previous two values, you don't need the full array — two rolling variables are enough.
public int robBruteForce(int[] nums) {
return helper(nums, nums.length - 1);
}
private int helper(int[] nums, int i) {
if (i < 0) return 0;
if (i == 0) return nums[0];
int skip = helper(nums, i - 1);
int rob = helper(nums, i - 2) + nums[i];
return Math.max(skip, rob);
}Time: O(2^n) without memoization · Space: O(n) recursion depth