Easy DP approach in C++( memoization )


#1
int helper(vector<vector<int>>&v,vector<vector<int>>&dp,bool &check,int row,int col)
{
    int n=v.size(),m=v[0].size();
    if(row<0 || col<0 || row>=n || col>=m)
    {
        return dp[row][col]=0;
    }
    if(row==n-1 && col==m-1)
    {
        check=true;
        return dp[row][col]=1;
    }
    int right=1;
    if(col+1<m && v[row][col]<v[row][col+1])
    {
        if(dp[row][col+1]==-1)
        {
            dp[row][col+1]=helper(v,dp,check,row,col+1);
        }
        right=1+dp[row][col+1];
    }
    int down=1;
    if(row+1<n && v[row][col]<v[row+1][col])
    {
        if(dp[row+1][col]==-1)
        {
            dp[row+1][col]=helper(v,dp,check,row+1,col);
        }
        down=1+dp[row+1][col];
    }
    return dp[row][col]=max(right,down);
}
int Solution::solve(vector<vector<int>>&A) 
{
    bool check=false;
    vector<vector<int>>dp(A.size(),vector<int>(A[0].size(),-1));
    int x=helper(A,dp,check,0,0);
    return check?x:-1;
}