题目

思路

• 记忆化搜索 + DFS
• dp[i][j]表示[i, j]位置所在的最长路径长度。如果下一次读到了已经读过的坐标，直接返回dp[i][j]即可，相当于新路接到了旧路上。
• dp[x][y] = max(dp[x][y], dfs(nx, ny) + 1,当前位置的最大值是在新路上接上一条老路，还是接着走老路。

  代码

  ```cpp

  include

using namespace std;

const int N = 3e2 + 5; int m[N][N]; int dp[N][N];

int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1};

int max_len = 0; int r, c;

bool valid(int x, int y, int row, int col) { if (x < 0 || x >= row) { return false; } if (y < 0 || y >= col) { return false; } return true; }

int dfs(int x, int y) { // 防止重复读 if (dp[x][y] != 0) { return dp[x][y]; }

for (int i = 0; i < 4; ++i) {
    int nx = x + dx[i], ny = y + dy[i];
    if (!valid(nx, ny, r, c)) {
        continue;
    }
    if (m[nx][ny] >= m[x][y]) {
        continue;
    }
    dp[x][y] = max(dfs(nx, ny) + 1, dp[x][y]);
}
return dp[x][y];

}

int main() { cin >> r >> c;

for (int i = 0; i < r; i++) {
    for (int j = 0; j < c; j++) {
        int temp = 0;
        cin >> temp;
        m[i][j] = temp;            
    }
}

int max_len = 0;
for (int i = 0; i < r; ++i) {
    for (int j = 0; j < c; ++j) {
        int len = dfs(i, j);
        max_len = max(max_len, len);
    }
}

printf("%d\n", max_len + 1);
return 0;

} ```