Accepted Java Solution with DP explaination


  • 0
    P

    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];
    }
    

    }


Log in to reply
 

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