Easy DP based solution (C++)


#1

int Solution::solve(vector<vector > &A) {
//n rows, m columns
int n = A.size(), m = A[0].size();
int dp[n][m] = {0};
dp[0][0] = 1;
int i = 1, j = 1;
while(i < m) {
if(A[0][i] > A[0][i - 1]) {
dp[0][i] = 1 + dp[0][i - 1];
i++;
}
else {
while(i < m)
dp[0][i++] = 0;
}
}

while(j < n) {
    if(A[j][0] > A[j - 1][0]) {
        dp[j][0] = 1 + dp[j - 1][0];
        j++;
    }
    else {
        while(j < n)
            dp[j++][0] = 0;
    }
}

for(i = 1; i < n; i++) {
    for(j = 1; j < m; j++) {
        if(A[i][j] > A[i - 1][j] && dp[i - 1][j] != 0)
            dp[i][j] = 1 + dp[i - 1][j];
        if(A[i][j] > A[i][j - 1] && dp[i][j - 1] != 0)
            dp[i][j] = max(dp[i][j], 1 + dp[i][j - 1]);
        else
            dp[i][j] = 0;
    }
}
return dp[n - 1][m - 1] == 0 ? -1 : dp[n - 1][m - 1];

}