# Accepted Java Solution with DP explaination

• The robber can't rob adjacent houses. i.e if he robs from the nth house he cannot rob from (n-1) th house and if he robs from (n-1)th house he cannot rob from the nth and (n-2) th house. So, he should select which ever choice will eventually lead to more money he can rob. We have to take Max (robbing nth house + maximum sum that can be obtained till (n-2)th house, robbing(n-1)th house (not robbing nth house) + maxSum that can be obtained by robbing till (n-3)th house).

Memotization is used in the code.

///

public class Solution {

``````int[] maxSum;
public int rob(int[] nums) {
if(nums.length == 0) return 0;
if(nums.length == 1) return nums[0];
if(nums.length == 2) return Math.max(nums[0], nums[1]);
maxSum = new int[nums.length];
maxSum[0] = nums[0];
maxSum[1] = Math.max(nums[0], nums[1]);
for(int i = 2 ; i < nums.length ; i++){
maxSum[i] = -1;
}
return robSum(nums,nums.length - 1);
}

public int robSum(int[] nums, int n){
if(n < 0) return 0;
if(n == 0) return nums[0];
if(n == 1) return nums[1];
if(n == 2) return Math.max(nums[n] + nums[n-2] , nums[n-1]);
if(maxSum[n-2] == -1){
maxSum[n-2] = robSum(nums, n-2);
}
if(maxSum[n-3] == -1){
maxSum[n-3] = robSum(nums, n-3);
}
if(maxSum[n] == -1){
maxSum[n] =  Math.max(nums[n] + maxSum[n-2], nums[n-1] + maxSum[n-3]);
}
return maxSum[n];
}
``````

}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.