Python 3 simple solution O(n) time, O(n) space


#1
def solve(self, A):
    dp = [[0]*(len(A[0])+1) for _ in range(len(A)+1)]
    
    for i in range(len(A)):
        for j in range(len(A[0])):
            if i==0 and j==0:
                dp[i+1][j+1] = 1
            elif i==0 and A[i][j]>A[i][j-1] and dp[i+1][j]:
                dp[i+1][j+1] = dp[i+1][j]+1
            elif j==0 and A[i][j]>A[i-1][j] and dp[i][j+1]:
                dp[i+1][j+1] = dp[i][j+1]+1
            else:
                if A[i][j]>A[i-1][j] and A[i][j]>A[i][j-1] and (dp[i+1][j] or dp[i][j+1]):
                    dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1])+1
                elif A[i][j]>A[i-1][j] and dp[i][j+1]:
                    dp[i+1][j+1] = dp[i][j+1]+1
                elif A[i][j]>A[i][j-1] and dp[i+1][j]:
                    dp[i+1][j+1] = dp[i+1][j]+1
    return dp[len(A)][len(A[0])] if dp[len(A)][len(A[0])]!=0 else -1`