如何在网格中找到增加数字的最长路径？

Question

假设我们有一个网格:

1 5 7
3 4 9
6 2 8

解决方案是:1-3-4-5-7-9

怎么解决这个问题？

Answer 1

我认为这个问题可以使用递归dp来解决.只需记住从特定点开始获得的最长路径的长度.

int dp[rows][cols]={0};
int dfs(int x , int y , int val)
    {
       if(dp[i][j] != 0 ) // already visited
        return dp[i][j];
       int lengthoflongestpath = 0;
       Search in four directions in the grid for the element greater than val; // Say newx, newy,newval
       lengthoflongestpath = max(lengthoflongestpath , dfs( newx , newy , newval));
       lengthoflongestpath ++; // add that particular element to the path
       dp[x][y] = lengthoflongestpath;
       return dp[x][y];
    }


int ans = 0;   
for(i=0 to rows)
 for(j=0 to cols)
   if(dp[i][j] == 0) // unvisited
    {
     dp[i][j] = dfs(i,j,grid[i][j]);
     ans = max(ans,dp[i][j]);
    }
 PRINT ans;

这将返回最长路径的长度.为了打印确切的路径,我们需要使用NEXT ARRAY并存储下一个元素,该元素相应地返回最大的"lenghtofthelongestpath".

复杂性:行*Cols

编辑:如何在4个方向搜索.

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 and newy lie inside the grid and newval > val)
        dfs(newx,newy,newval);
 }