Maximum sum of non-adjacent elements

//I am going to solve this question by 4 method



class Solution {
public:
// 1st Method RECURSIVE SOLUTION

   int solve(vector<int>&nums, int n){
   
   //base condition
   if(n<0)
   return 0;
   
   if(n==0)
   return nums[0];
   
   int incl=solve(nums,n-2)+nums[n];
   int excl= solve(nums,n-1) +0;
   
   return max(incl, excl);
   
   }
   
   int maximumNonAdjacentSum(vector<int>&nums) {
   
   int n=nums.size();
   
   int ans= solve(nums,n-1);
   
   return ans;
   }
     

};

//2nd Method: RECURSION+ MEMOIZATION

int solveMem(vector<int>&nums,int n, vector<int>&dp){
 
 //base condition
 
  if(n<0)
   return 0;
   
   if(n==0)
   return nums[0];
   
   if(dp[n]!=-1)
   return dp[n];
   
   int incl=solveMem(nums,n-2)+nums[n];
   int excl= solveMem(nums,n-1) +0;
   
   dp[n]=max(incl,excl);
   return dp[n];
   }
   
   int maximumNonAdjacentSum(vector<int>&nums){
   int n=nums.size();
   vector<int>dp(n,-1);
   return solveMem(nums,n-1,dp);
   }
   
   //3rd Method: TABULATION
   
   int solveTab(vector<int>&nums){
   int n=nums.size();
   
   vector<int>dp(n,0);
   
   dp[0]=nums[0];
   
   for(int i=1; i<n; i++){
    int incl=dp[i-2]+nums[i];
    int excl= dp[i-1]+ 0;
    
    dp[i]= max(incl,excl);
    }
    return dp[n-1];
    }
    
    int maximumNonAdjacentSum(vector<int>&nums){
   int n=nums.size();
  
   return solveTab(nums);
   }
   
   
   //4th Method: Space Opimisation
   
   
   
   int solveSo(vector<int>&nums){
   int n=nums.size();
   
   int prev2=0;
   int prev1=nums[0];
   
   for(int i=1; i<n; i++){
   int incl=prev2+nums[i];
   int excl=prev1+0;
   int ans=max(incl,excl);
   prev2=prev1;
   prev1=ans;
   }
   return prev1;
   }
   
  int maximumNonAdjacentSum(vector<int>&nums){
   int n=nums.size();
  
   return solveSo(nums);
   }
   
   
   //THANKS FOR READING HOPE YOU ENJOY IT