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