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