1340-JUMP GAME V SOLUTION.txt

class Solution {
public:int d;
    int max(int a,int b){
        return a>b?a:b;
    }
    int fun(vector< int>&v,int i,vector< int>&dp){
        if(i>=v.size()||i<0)return 0;
        if(dp[i]!=-1)return dp[i];
        int res=0;
        int j;
        for(j=i+1;j<v.size()&&v[j]<v[i]&&j<=i+d;j++){
        res=max(res,1+fun(v,j,dp));
        }
        for(j=i-1;j>=0&&v[j]<v[i]&&j>=i-d;j--){
        res=max(res,1+fun(v,j,dp));
        }
        return dp[i]=res;
        
        
    }
    
    
    int maxJumps(vector<int>& arr,int d1) {
       // vector<int>val,a;
        d=d1;
       
        
        int ans=0;vector<int>dp(arr.size(),-1);
      for(int i=0;i<arr.size();i++){
        ans=max(ans,fun(arr,i,dp));
      }
        return ans+1;
    }
};