Java DFS+DP solution


#1
public class Solution {
boolean flag=false;
int[][] dir={{0,1},{1,0}};
public int solve(int[][] A) {
    if(A==null || A.length==0)  return 0;
    if(A.length==1) return 1;
    int[][] dp=new int[A.length][A[0].length];
    int res=dfs(A,0,0,dp);
    if(!flag)   return -1;
    return res;
}
int dfs(int[][] A,int i,int j,int[][] dp){
    if(i==A.length-1 || j==A[0].length-1)    flag=true;
    if(dp[i][j]!=0)
        return dp[i][j];
    dp[i][j]=1;
    for(int[] d:dir){
        int x=d[0]+i;
        int y=d[1]+j;
        if(x<0 || x>=A.length || y<0 || y>=A[0].length || A[x][y]<A[i][j]){
            continue;
        }
        dp[i][j]=Math.max(dp[i][j],dfs(A,x,y,dp)+1);
    }
    return dp[i][j];
}

}