House Robber II

shriyanshi24jindal

Mar 28th, 2026

Never

Not a member of GistPad yet? Sign Up, it unlocks many cool features!

Java 11.40 KB | None | 0 0

copy raw download clone embed print report

class Solution {
/** Recursion */
public int rob(int[] nums) {
int n = nums.length;
return findMaxCost(nums, n);
}
public int findMaxCost(int[] nums, int n)
{
// because at index=0, there is a house but it's adjacent so we cannot count the cost
if(n == 0)
return 0;
if(n == 1)
return 1;
// pick the house and ignore the adjacents
int pick = nums[n-1] + findMaxCost(nums, n-2);
// do not pick the house and ignore the current house
int notPick = findMaxCost(nums, n-1);
return Math.max(pick, notPick);
}
/** Memoization
So, just like I mentioned before, handle two ranges:
nums[0..n-2] → include first house, exclude last
nums[1..n-1] → exclude first house, include last
*/
public int rob(int[] nums) {
int n = nums.length;
if (n == 1)
return nums[0];
// include first house, exclude last
int[] t1 = new int[n+1];
Arrays.fill(t1, -1);
int case1 = findMaxCost(nums, 0, n - 2, t1);
// include last house, exclude first
int[] t2 = new int[n+1];
Arrays.fill(t2, -1);
int case2 = findMaxCost(nums, 1, n - 1, t2);
return Math.max(case1, case2);
}
public int findMaxCost(int[] nums, int start, int end, int[] t)
{
// because at index=0, there is a house but it's adjacent so we cannot count the cost
if(start > end)
return 0;
if(t[end] != -1)
return t[end];
// pick the house and ignore the adjacents
int pick = nums[end] + findMaxCost(nums, start, end-2, t);
// do not pick the house and ignore the current house
int notPick = findMaxCost(nums, start, end-1, t);
t[end] = Math.max(pick, notPick);
return t[end];
}
}

RAW Paste Data Copied

class Solution {
    /** Recursion */
    public int rob(int[] nums) {
        int n = nums.length;

return findMaxCost(nums, n);
    }

public int findMaxCost(int[] nums, int n)
    {
        // because at index=0, there is a house but it's adjacent so we cannot count the cost
        if(n == 0)
            return 0;
        if(n == 1)
            return 1;
        
        // pick the house and ignore the adjacents
        int pick = nums[n-1] + findMaxCost(nums, n-2);
        // do not pick the house and ignore the current house
        int notPick = findMaxCost(nums, n-1);

return Math.max(pick, notPick);
    }
    
    /** Memoization 
    So, just like I mentioned before, handle two ranges:
    nums[0..n-2] → include first house, exclude last
    nums[1..n-1] → exclude first house, include last
    */
    public int rob(int[] nums) {
        int n = nums.length;

if (n == 1)
            return nums[0];

// include first house, exclude last
        int[] t1 = new int[n+1];
        Arrays.fill(t1, -1);
        int case1 = findMaxCost(nums, 0, n - 2, t1);

// include last house, exclude first
        int[] t2 = new int[n+1];
        Arrays.fill(t2, -1);
        int case2 = findMaxCost(nums, 1, n - 1, t2);

return Math.max(case1, case2);
    }

public int findMaxCost(int[] nums, int start, int end, int[] t)
    {
        // because at index=0, there is a house but it's adjacent so we cannot count the cost
        if(start > end)
            return 0;
        
        if(t[end] != -1)
            return t[end];
        
        // pick the house and ignore the adjacents
        int pick = nums[end] + findMaxCost(nums, start, end-2, t);
        // do not pick the house and ignore the current house
        int notPick = findMaxCost(nums, start, end-1, t);

t[end] = Math.max(pick, notPick);
        return t[end];
    }
}