Increasing Path in Matrix

• Time : $O(nm)$
• Space : $O(nm)$

int Solution::solve(vector<vector<int> > &A) {
    int n = A.size(), m = A[0].size();
    vector<vector<long long>> dp(n, vector<long long>(m, -1));
    dp[0][0] = 1;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(dp[i][j] == -1) continue;
            if(i + 1 < n and A[i][j] < A[i+1][j]) {
                dp[i+1][j] = max(dp[i+1][j], dp[i][j] + 1);
            }
            if(j + 1 < m and A[i][j] < A[i][j+1]) {
                dp[i][j+1] = max(dp[i][j+1], dp[i][j] + 1);
            }
        }
    }
    return dp[n-1][m-1];
}