DP - similar to max_sum_path - #steps is always constant (r+c-1)


#1
 int r = A.size(), c = A[0].size();
vector < vector <int> > dp(r, vector <int> (c,0));
for(int i=0;i<r;i++)
{
    for(int j=0;j<c;j++)
    {
        bool f = true;
        if(i==0 && j==0)
            dp[i][j] = A[i][j];
        else
        {
            if(i>=1 && A[i][j] > A[i-1][j] && dp[i-1][j] >=0)
                f=false,dp[i][j] =  dp[i-1][j];
            if(j>=1 && A[i][j] > A[i][j-1] && dp[i][j-1]>=0)
                f=false,dp[i][j] = max(dp[i][j], dp[i][j-1]);
            dp[i][j] += A[i][j];
            if(f)
                dp[i][j] = INT_MIN;
            
            
        }   
    }
}
if(dp[r-1][c-1] < 0)
    return -1;
return r+c-1;