题意：给你一个R*C的矩阵，每个元素代表这一小格的h，只能往上下左右四个方向走，每次只能往高度小于当前格h的方向走，求能走的最长路径
数据范围：1 <= R,C <= 100 , 0 <= h <= 10000
思路：裸LIS，只不过是二维的，感觉这种走迷宫，矩阵形状的写记忆化比递推方便而且自然
dp[ i ][ j ] = max(dp[ i-1 ][ j ], dp[ i+1 ][ j ], dp[ i ][ j-1 ], dp[ i ][ j+1 ]) + 1
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 5 const int mx = 110; 6 int a[mx][mx], dp[mx][mx]; 7 int dr[] = {-1, 0, 1, 0}; 8 int dc[] = {0, -1, 0, 1}; 9 int n, m; 10 11 int dfs(int r, int c){ 12 int sum = 1; 13 if (dp[r][c] > 0) return dp[r][c]; 14 for (int i = 0; i < 4; i++){ 15 int x = r+dr[i]; 16 int y = c+dc[i]; 17 if (x <= 0 || x > n || y <= 0 || y > m) continue; 18 if (a[x][y] > a[r][c]) 19 sum = max(sum, dfs(x, y)+1); 20 } 21 return dp[r][c] = sum; 22 } 23 24 int main(){ 25 scanf("%d%d", &n, &m); 26 for (int i = 1; i <= n; i++) 27 for (int j = 1; j <= m; j++) 28 scanf("%d", &a[i][j]); 29 int ans = 0; 30 for (int i = 1; i <= n; i++){ 31 for (int j = 1; j <= m; j++){ 32 dp[i][j] = dfs(i, j); 33 ans = max(ans, dp[i][j]); 34 } 35 } 36 printf("%d ", ans); 37 return 0; 38 }