Easy memorization+ recursive soution


#1

int sol(vector<vector>&a,int n,int m,int i,int j,intdp)
{
if(i==n-1&&j==m-1)
{
return 1;
}
if(dp[i][j]!=-1)
{
return dp[i][j];
}
int ans1=INT_MIN;
int ans2=INT_MIN;
if(i+1<n)
{
if(a[i+1][j]>a[i][j])
{
ans1=1+sol(a,n,m,i+1,j,dp);
}
}
if(j+1<m)
{
if(a[i][j+1]>a[i][j])
{
ans2=1+sol(a,n,m,i,j+1,dp);
}
}
dp[i][j]=max(ans1,ans2);
return dp[i][j];
}
int Solution::solve(vector<vector > &a) {
int n=a.size();
int m=a[0].size();
int
dp=new int*[n+1];
for(int i=0;i<=n;i++)
{
dp[i]=new int[m+1];
for(int j=0;j<=m;j++)
{
dp[i][j]=-1;
}
}
int ans=sol(a,n,m,0,0,dp);
for(int i=0;i<=n;i++)
{
delete []dp[i];
}
delete []dp;
if(ans<0)
{
return -1;
}
else
{
return ans;
}
}