House Robber

shriyanshi24jindal

Mar 28th, 2026

Never

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

Java 13.24 KB | None | 0 0

copy raw download clone embed print report

class Solution {
/** Recursive code */
public int rob(int[] nums) {
int n = nums.length;
return findMaxAmount(nums, n);
}
public int findMaxAmount(int[] nums, int n)
{
// no houses left
if(n == 0)
return 0;
// only one house
if(n == 1)
return nums[0];
// pick the house and ignore the adjacents
int pick = nums[n-1] + findMaxAmount(nums, n-2);
// do not pick the house and ignore the current house
int notPick = findMaxAmount(nums, n-1);
return Math.max(pick, notPick);
}
/** Memoization code */
public int rob(int[] nums) {
int n = nums.length;
int[] t = new int[n+1];
Arrays.fill(t, -1);
return findMaxAmount(nums, n, t);
}
public int findMaxAmount(int[] nums, int n, int[] t)
{
// no houses left
if(n == 0)
return 0;
// only one house
if(n == 1)
return nums[0];
if(t[n] != -1)
return t[n];
// pick the house and ignore the adjacents
int pick = nums[n-1] + findMaxAmount(nums, n-2, t);
// do not pick the house and ignore the current house
int notPick = findMaxAmount(nums, n-1, t);
t[n] = Math.max(pick, notPick);
return t[n];
}
/** Top-down approach */
public int rob(int[] nums) {
int n = nums.length;
int[] t = new int[n+1];
// initalise array with base condition
// only one house
t[0] = 0;
// only one house: because at index=0, there is a house which has a cost
t[1] = nums[0];
for(int i=2; i<n+1; i++)
{
int pick = nums[i-1] + t[i-2];
int notPick = t[i-1];
t[i] = Math.max(pick, notPick);
}
return t[n];
}
}

RAW Paste Data Copied

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

return findMaxAmount(nums, n);
    }

public int findMaxAmount(int[] nums, int n)
    {
        // no houses left
        if(n == 0) 
            return 0;
        
        // only one house
        if(n == 1) 
            return nums[0];
        
        // pick the house and ignore the adjacents
        int pick = nums[n-1] + findMaxAmount(nums, n-2);
        // do not pick the house and ignore the current house
        int notPick = findMaxAmount(nums, n-1);

return Math.max(pick, notPick);
    }
    
    /** Memoization code */
    public int rob(int[] nums) {
        int n = nums.length;

int[] t = new int[n+1];
        Arrays.fill(t, -1);

return findMaxAmount(nums, n, t);
    }

public int findMaxAmount(int[] nums, int n, int[] t)
    {
        // no houses left
        if(n == 0) 
            return 0;
        
        // only one house
        if(n == 1) 
            return nums[0];
        
        if(t[n] != -1)
            return t[n];
        
        // pick the house and ignore the adjacents
        int pick = nums[n-1] + findMaxAmount(nums, n-2, t);
        // do not pick the house and ignore the current house
        int notPick = findMaxAmount(nums, n-1, t);

t[n] = Math.max(pick, notPick);
        return t[n];
    }
    
    /** Top-down approach */
    public int rob(int[] nums) {
        int n = nums.length;

int[] t = new int[n+1];

// initalise array with base condition
        // only one house
        t[0] = 0;
        // only one house: because at index=0, there is a house which has a cost
        t[1] = nums[0];

for(int i=2; i<n+1; i++)
        {
            int pick = nums[i-1] + t[i-2];
            int notPick = t[i-1];
            t[i] = Math.max(pick, notPick);
        }
        return t[n];
    }
}