Java easy solution using bottom up dp

interview-questions
programming
google
Tags: #<Tag:0x00007f242751bd80> #<Tag:0x00007f242751bc18> #<Tag:0x00007f242751bab0>

#1

In case you guys have any doubt regarding my approach feel free to comment down,and I will surely reply!!

CODE:

public class Solution {
public int solve(int[][] A) {
int n=A.length;
int m=A[0].length;

    int[][] dp=new int[n][m];
    //1st row
    dp[0][0]=1;
    for(int i=1;i<m;i++)
    {
       if(A[0][i-1]<A[0][i])
        dp[0][i]= dp[0][i-1]+1;
        
        else
        {
            return -1;
        }
       
    }
    for(int i=1;i<n;i++)
    {
         if(A[i-1][0]<A[i][0])
         dp[i][0]=dp[i-1][0]+1;
         
         else
         {
             return -1;
         }
         
    }
    for(int i=1;i<n;i++)
    {
        for(int j=1;j<m;j++)
        {
            if(A[i-1][j]<A[i][j] && A[i][j-1]<A[i][j])
            {
                dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1])+1;
            }
            else if(A[i-1][j]<A[i][j] && A[i][j-1]>A[i][j])
            {
                dp[i][j]=dp[i-1][j]+1;
            }
            else
            {
                dp[i][j]=dp[i][j-1]+1;
            }
        }
    }
    return dp[n-1][m-1]==0?-1:dp[n-1][m-1];
    
}

}