Easy dp approach


#1

int Solution::solve(vector<vector > &a) {
int i,j;
int n=a.size(),m=a[0].size();
int dp[n][m];
memset(dp,0,sizeof(dp));
dp[0][0]=1;
for(i=1;i<n;i++){
if(a[0][i]>a[0][i-1]) dp[0][i]=1+dp[0][i-1];
else break;
}
for(j=1;j<m;j++){
if(a[j][0]>a[j-1][0]) dp[j][0]=1+dp[j-1][0];
else break;
}
for(i=1;i<n;i++){
for(j=1;j<m;j++){
if(a[i][j]>a[i-1][j]) dp[i][j]=1+dp[i-1][j];
if(a[i][j]>a[i][j-1]) dp[i][j]=max(dp[i][j],1+dp[i][j-1]);
}
}
if(dp[n-1][m-1]==n+m-1) return n+m-1;
else return -1;

}