Problem
You are given an integer arraynums, where nums[i] represents the amount of money in the ith house.
You cannot rob two adjacent houses, as doing so will trigger the alarm. Return the maximum amount of money you can rob without robbing two adjacent houses.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
nums = [2,7,9,3,1]Output
12Solution
This problem can be solved using Memoization. For each house, we have two choices: rob the current house or skip the current house.If we rob house
i, we cannot rob the next house, so we continue from i + 2. If we skip it, we continue from i + 1.
Therefore:
rob(i) = max(nums[i] + rob(i + 2), rob(i + 1))0.
The same index can be reached multiple times, so we store previously calculated results in a memoization array.
class Solution {
public int rob(int[] nums) {
int n = nums.length;
int[] memo = new int[n];
Arrays.fill(memo, -1);
return Math.max(
letsRob(nums, 0, memo),
letsRob(nums, 1, memo)
);
}
private int letsRob(int[] nums, int i, int[] memo) {
// No houses left.
if (i >= nums.length) {
return 0;
}
// Return the cached result.
if (memo[i] != -1) {
return memo[i];
}
// Rob or skip the current house.
return memo[i] = Math.max(
nums[i] + letsRob(nums, i + 2, memo),
letsRob(nums, i + 1, memo)
);
}
}
Complexity
Each house is calculated only once, resulting inO(n) time complexity. The memoization array and recursion stack require O(n) space.
Tabulation Approach
Instead of starting from the first house and recursively exploring future houses, we can build the solution from left to right.At each house, we again have two choices: rob the current house and add its value to the maximum amount from two houses earlier, or skip the current house and keep the maximum amount from the previous house.
Therefore:
dp[i] = max( nums[i] + dp[i - 2], dp[i - 1] )dp[0] = nums[0] dp[1] = max(nums[0], nums[1])public int rob(int[] nums) {
if (nums.length == 1) {
return nums[0];
}
int[] dp = new int[nums.length];
// Maximum amount after the first house.
dp[0] = nums[0];
// Rob either the first or second house.
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < nums.length; i++) {
// Rob or skip the current house.
dp[i] = Math.max(nums[i] + dp[i - 2], dp[i - 1]);
}
return dp[nums.length - 1];
}
Complexity
Each house is processed once, resulting inO(n) time complexity. The DP array stores one value for each house, requiring O(n) space.
Space Optimized Approach
In the tabulation approach, the result for the current house depends only on the previous two values. Therefore, we do not need to store the entire DP array.We keep two variables representing the maximum amount from the previous two positions.
public int rob(int[] nums) {
int previousTwo = 0;
int previousOne = 0;
for (int money : nums) {
// Rob the current house or skip it.
int current = Math.max(previousOne, money + previousTwo);
previousTwo = previousOne;
previousOne = current;
}
return previousOne;
}
Complexity
Each house is processed once, resulting inO(n) time complexity. Only two variables are used, reducing the extra space complexity to O(1).