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