Memoized Solution


#1

int dp[1002][1002];
int valid(int i , int j, int n, int m , vector<vector >&A ){
return i>=0&&j>=0&&i<n&&j<m;
}
int find(vector<vector > & A, int i, int j, int path, int n, int m){

if(i==n-1&&j==m-1) return 1;

int & ans = dp[i][j];
if(ans!=0) return ans;

 if(valid(i,j+1,n,m, A)&& A[i][j+1]>A[i][j])
  {int p =  find(A,i,j+1,path,n,m);
    if(p!=0) ans=max(ans,p);}
  if(valid(i+1,j,n,m, A)&& A[i+1][j]>A[i][j])
{   int p = find(A,i+1,j,path,n,m);
     if(p!=0) ans = max(ans,p);}

if(ans==0) return 0;
return ans+1;
}
int Solution::solve(vector<vector > &A) {
memset(dp,0,sizeof(dp));
int n = A.size();
int m = A[0].size();
int a = find(A,0,0,0,n,m);

if(a==0) return -1;
return a;

}