• DP问题一定不能出现环，一定是拓扑结构

    image.png

    • 本质就是利用递归，因为当前的i,j是基于上下左右的最大值，如果上下左右能走，代表值 + 1
    1. #include <iostream>
    2. #include <algorithm>
    3. #include <cstring>
    5. using namespace std;
    7. const int N = 610;
    8. int n, m;
    9. int f[N][N], h[N][N];
    11. int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; // 表示上下左右四个点
    13. int dp(int x, int y)
    14. {
    15.     int &v = f[x][y]; // 引用的v就是f[x][y]，简化代码
    16.     if (v != -1) return v; // 只要算一遍就行，如果查的x,y不是-1直接返回对应的值就可以
    17.     v = 1; // 因为开始的点很有可能没有能走的点，但是初始值也得是1
    18.     for (int i = 0; i < 4; i++)
    19.     {
    20.         int a = dx[i] + x, b = dy[i] + y;
    21.         if (a >= 1 && a <= n && b >= 1 && b <= m && h[a][b] < h[x][y])
    22.             v = max(v, dp(a, b) + 1); // 找出周围四个点最大的那个
    23.     }
    24.     return v;
    25. }
    27. int main()
    28. {
    29.     ios::sync_with_stdio(false);
    30.     cin >> n >> m;
    31.     for (int i = 1; i <= n; i++)
    32.         for (int j = 1; j <= m; j++)
    33.             cin >> h[i][j];
    35.     memset(f, -1, sizeof f);
    37.     int res = 0;
    38.     for (int i = 1; i <= n; i++)
    39.         for (int j = 1; j <= m; j++)
    40.             res = max(res, dp(i, j));
    41.     cout << res << endl;
    42.     return 0;
    43. }