algorithm - how to find the longest path of increasing numbers in a grid? -

this question has answer here:

• longest increasing sequence 2d matrix recursion 4 answers

assuming have grid:

1 5 7 3 4 9 6 2 8 

the solution be: 1-3-4-5-7-9

how solved?

i think problem can solved using recursive dp. memoise lenght of longest path obtained starting @ particular point.

int dp[rows][cols]={0}; int dfs(int x , int y , int val)     {        if(dp[i][j] != 0 ) // visited         return dp[i][j];        int lengthoflongestpath = 0;        search in 4 directions in grid element greater val; // newx, newy,newval        lengthoflongestpath = max(lengthoflongestpath , dfs( newx , newy , newval));        lengthoflongestpath ++; // add particular element path        dp[x][y] = lengthoflongestpath;        return dp[x][y];     }   int ans = 0;    for(i=0 rows)  for(j=0 cols)    if(dp[i][j] == 0) // unvisited     {      dp[i][j] = dfs(i,j,grid[i][j]);      ans = max(ans,dp[i][j]);     }  print ans; 

this returns length of longest path. printing exact path need use next array , store next element returns maximum "lenghtofthelongestpath" accordingly.

complexity : rows * cols

edit : how search in 4 directions.

int dx[] = {1,-1,0,0}; int dy[] = {0,0,1,-1};  for(int i=0; i<4; i++)  {       int newx = x + dx[i];       int newy = y + dy[i];       if(newx , newy lie inside grid , newval > val)         dfs(newx,newy,newval);  }