DP #213 House Robber II

class Solution {
    public int rob(int[] nums) {

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


        int[] nums1 = Arrays.copyOfRange(nums,0,n-1);
        int[] nums2 = Arrays.copyOfRange(nums,1,n);

        // int[] dp = new int[n-1];
        // Arrays.fill(dp,-1);
        // recur(n-2,nums1, dp);
        // int ans = dp[n-2];
        // Arrays.fill(dp,-1);
        // recur(n-2,nums2, dp);
        // ans = Math.max(ans, dp[n-2]);

        int ans = tabOpt(nums1,n-1);
        ans = Math.max(ans, tabOpt(nums2,n-1));
        return ans;
    }

    // Tabulation Space Optimised Solution
    int tabOpt(int[] nums,int n){
        int prev=nums[0];
        int prev2 = 0;

        for(int i=1; i<n; i++){
            int tk = nums[i] + ((i-2 >= 0) ? prev2: 0);
            int ntk = prev;
            int cur = Math.max(tk,ntk);
            prev2 = prev;
            prev = cur;
        }

        return prev;
    }

    // Tabulation Solution
    int tab(int[] nums,int n){

        int[] dp = new int[n];
        Arrays.fill(dp,-1);
        dp[0]=nums[0];

        for(int i=1; i<n; i++){
            int tk = nums[i] + ((i-2 >= 0) ? dp[i-2]: 0);
            int ntk = dp[i-1];
            dp[i] = Math.max(tk,ntk);
        }

        return dp[n-1];
    }

    // Recursion Memoization Solution
    int recur(int i, int[] nums, int[] dp){
        if(i == 0) return dp[i] = nums[i];
        if(i < 0) return 0;
        if(dp[i] != -1) return dp[i];

        int tk = nums[i] + func(i-2, nums, dp);
        int ntk = func(i-1, nums, dp);

        return dp[i] = Math.max(tk,ntk);
    }
}