Q-5 House Robber - LeetCode 198

class Solution {
    //https://www.youtube.com/watch?v=GrMBfJNk_NY&list=PLgUwDviBIf0qUlt5H_kiKYaNSqJ81PMMY&index=6&ab_channel=takeUforward
    public int rob(int[] nums) {
        int n = nums.length;
        
        //recursion
        // return solve1(nums ,n-1);   
        
        //recursion + memoization
        // dp = new Integer[n];
        // return solve2(nums , n-1);

        //tabulation -> 2*n | Sc - n
        int dp[]= new int[n];
        dp[0] = nums[0];

        for(int i = 1 ;i < n ; i++){
            
           int pick = nums[i] + (i-2 >= 0 ? dp[i-2] : 0);

            int notpick = 0 + dp[i-1];

            dp[i] = Math.max(pick ,notpick);
        }
        return dp[n-1];
    }

    //recursion
    public int solve1(int nums[] , int idx){
        if(idx == 0)
        return nums[0];

        if(idx < 0 )
        return 0;

        int pick = nums[idx] + solve1(nums ,idx-2);
        int notpick = 0 + solve1(nums , idx - 1);

        return Math.max(pick , notpick);
    }

    //recursion 2^n + memoization 2*n + Sc- n + n  
    Integer dp[];
    public int solve2(int nums[] , int idx){
        if(idx == 0)
        return nums[0];

        if(idx < 0 )
        return 0;

        if(dp[idx] != null)
        return dp[idx];

        int pick = nums[idx] + solve2(nums ,idx-2);
        int notpick = 0 + solve2(nums , idx - 1);

        return dp[idx] = Math.max(pick , notpick);
    }
}