动态规划

递归关系

  • 状态表示f[i,j]
    • 集合：从前i个物品选且体积小于j
    • 属性：最大值，最小代价，数量
  • 状态计算——集合划分

01 背包

  • 每件物品可以用一次

  • 不包含第i个物品：f(i - 1, j)

  • 包含第i个物品：f(i - 1,j - vi) + wi 空余一个vi的位置，加上第i个物品的权重

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <algorithm>
#include <iostream>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N]; //体积和价值
int f[N][N]; //第一个N表示取第1~n个物品，第二个n表示从1开始到m的容量

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++)
    cin >> v[i] >> w[i];

  for (int i = 1; i <= n; i++)   //从一个物品开始取
    for (int j = 1; j <= m; j++) //逐渐增大背包容量至m
    {

      f[i][j] = f[i - 1][j];    //不取第i个物品
      if (j >= v[i])            //若有空间，比较取第i个物品和不取第i个物品的最大值
        f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
    }
  cout << f[m][n] << ' ';
  return 0;
}


4 5
1 2
2 4
3 4
4 5
// 物品是由小到大排列的
v[i] = 1 2 3 4
w[i] = 2 4 4 5
    1 2 3 4 5       j
0   0 0 0 0 0
1   2 2 2 2 2   
2   2 4 6 6 6 
3   2 4 6 6 8 
4   2 4 6 6 8


i

滚动数组写法:

  • 为什么要从后向前更新：因为当你计算 f[j] 时，f[j-v[i]] 可能已经被当前物品 i 更新过了。这意味着你可能会在同一轮次中多次使用同一个物品，违背了 0/1 背包的要求。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <algorithm>
#include <iostream>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N]; //体积和价值
int f[N]; //采用滚动数组，滚动数组的本质还是减少空间复杂度

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++)
    cin >> v[i] >> w[i];

  for (int i = 1; i <= n; i++)      //从一个物品开始取
    for (int j = m; j >= v[i]; j--) //从后向前更新
    {
      // f[j] = f[j];
      f[j] = max(f[j], f[j - v[i]] + w[i]);
    }
  cout << f[m] << ' ';
  return 0;
}

完全背包

  • 每个物品有无限个

  • 状态表示f[i,j]

    • 集合
    • 属性

  • 状态计算——集合划分

  • f[i,j] = f[i - 1,j - v[i] k] + w[i] k

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <algorithm>
#include <iostream>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N][N];

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++)
    cin >> v[i] >> w[i];

  for (int i = 1; i <= n; i++)
    for (int j = 0; j <= m; j++) //正序更新,依赖于当前f[i]层的数据
      for (int k = 0; k * v[i] <= j; k++)
        f[i][j] = max(f[i][j],
                      f[i - 1][j - k * v[i]] + k * w[i]); //与01背包思想差不多

  cout << f[n][m] << endl;
  return 0;
}

优化，由于物品的数量是无限的，因此可以证明：

  • f[i,j] = Max(f[i][j], f[i-1,j-v]+w,f[i-1,j-2v]+2w,f[i-1,j-3v]+3w,...)等于f[i,j-v]
  • /f[i,j-v] = Max( ， f[i-1,j-v] ,f[i-1,j-2v]+w,f[i-1,j-3v]+2w,…)
  • f[i, j] = Max(f[i - 1, j], f[i, j - v] + w)
  • 正序更新的目的是让物品能够被多次使用。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <=  n; i ++ )  cin >> v[i] >> w[i];

    for (int i = 1;i <= n; i ++)
        for (int j = v[i]; j <= m; j ++ )          //正序更新,依赖于当前f[i]层的数据                  
                    f[j] = max(f[j], f[j - v[i]] + w[i]);
    cout << f[m] << endl;
    return 0;
}



完全背包与01背包的区别

  • 01背包：f[i, j] = max(f[i - 1, j], f[i - 1, j- v]+ w)

  • 完全背包：f[i,j] = max(f[i - 1, j], f[i, j - v] + w )

  • 循环开始位置不同：01背包是避免覆盖，完全背包是必须覆盖（滑动窗口）

多重背包

  • 每个物品有限个
  • 在完全背包的基础上限制物品数量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <algorithm>
#include <iostream>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N], s[N];
int f[N][N];

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++)
    cin >> v[i] >> w[i] >> s[i];

  for (int i = 1; i <= n; i++)
    for (int j = 0; j <= m; j++) //正序更新,依赖于当前f[i]层的数据
      for (int k = 0; k * v[i] <= j && k <= s[i]; k++)
        f[i][j] = max(f[i][j],f[i - 1][j - k * v[i]] + k * w[i]); 

  cout << f[n][m] << endl;
  return 0;
}

f[i,j] = f[i - 1,j - v[i] k] + w[i] k

不能装满，因此不能采用完全背包的优化

二进制优化：由于二进制$2^0……2^n$可以表示任意小于$2^n$的数，因此我们可以将一个物品拆成n

个二进制的物品

nlog2000

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 25000; // 1000 *log2 (200)

int n, m;
int v[N], w[N];

int f[N];

int main() {
  cin >> n >> m;
  int cnt = 0;
  for (int i = 1; i <= n; i++) {
    int a, b, s;
    cin >> a >> b >> s;
    int k = 1;
    while (k <= s) // 拆分为多个小背包
    {
      cnt++;
      v[cnt] = a * k; // 体积：原始体积 a 乘以 k
      w[cnt] = b * k; // 价值：原始价值 b 乘以 k
      s -= k;         // 减去已经处理的数量
      k *= 2;         // 乘以 2，进入下一个更大的子背包
    }
    if (s > 0) // 剩余部分作为一个小背包处理
    {
      cnt++;
      v[cnt] = a * s;
      w[cnt] = b * s;
    }
  } 
  
  //转化为01背包问题
  n = cnt;
  for (int i = 1; i <= n; i++)
    for (int j = m; j >= v[i]; j--)
      f[j] = max(f[j], f[j - v[i]] + w[i]);

  cout << f[m] << endl;

  return 0;
}

分组背包

  • 每组只能选一个

类似于01背包问题，我们只需添加组内遍历即可。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;         

int n, m;
int v[N][N], w[N][N], s[N];

int f[N];

int main()
{
    cin >> n >>m;
    for (int i = 1; i <= n; i ++)
    {
        cin >> s[i];
        for (int j = 1; j <= s[i]; j ++)
            cin >> v[i][j] >> w[i][j];
    }

    for (int i = 1; i <= n; i ++ )      //枚举所有组
        for (int j = m; j >= 0; j --)     //枚举所有背包组
            for (int k = 1; k <= s[i]; k ++ )       //枚举组内对象
                if (v[i][k] <= j)
                    f[j] = max(f[j], f[j-v[i][k]] + w[i][k]);

    cout << f[m] <<endl;
return 0;

}

线性dp

  • 递推顺序是线性的

AcWing 898. 数字三角形

image-20240809154516799

这题有两种解法：

  • 一种是像y总一样从上向下dp，然后对第n行的数据取最大值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510, INF = 1e9;

int n;
int a[N][N];
int f[N][N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= i; j ++ )
            scanf("%d", &a[i][j]);

    for (int i = 0; i <= n; i ++ )
        for (int j = 0; j <= i + 1; j ++ )
            f[i][j] = -INF;

    f[1][1] = a[1][1];
    for (int i = 2; i <= n; i ++ )		//注意边界
        for (int j = 1; j <= i; j ++ )
            f[i][j] = max(f[i - 1][j - 1] + a[i][j], f[i - 1][j] + a[i][j]);

    int res = -INF;
    for (int i = 1; i <= n; i ++ ) res = max(res, f[n][i]);

    printf("%d\n", res);
    return 0;
}
  • 另一种是从下往上dp，最后直接输出dp[1][1]即可，由于保证了左下右下两个数必定存在，因此不用初始化和减少了边界可能引发的问题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<iostream>
#include<cstdio> 
#include<cmath>
#include<map>
#include<algorithm>
using namespace std;
int dp[510][510];
int n;
int main()
{
  cin >> n;
  for (int i = 1; i <= n; i++)
  {
    for (int j = 1; j <= i; j++)
    {
      cin >> dp[i][j];
    }
  }
  for (int i = n - 1; i >= 1; i--)
  {
    for (int j = 1; j <= i; j++)
    {
      dp[i][j] = max(dp[i][j] + dp[i + 1][j], dp[i][j] + dp[i + 1][j + 1]);
    }
  }
  cout << dp[1][1] << endl;
  return 0;

}

AcWing 895. 最长上升子序列

我们维持到达每个位置的最长上升子序列，在枚举到下一元素时，对前面进行遍历寻求最长序列。

​ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>

using namespace std;

const int N = 1e5;
int a[N], dp[N];
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    for(int i = 0; i < n; i++)
    {
       dp[i] = 1;
       for(int j = 0; j < i; j++)
       {
            if(a[j] < a[i])
                dp[i] = max(dp[i], dp[j] + 1);
       }
    }
    int maxnum = -1e9;
    for(int i = 0; i < n; i++)
    {
        maxnum = max(maxnum, dp[i]);
    }
    cout<< maxnum << endl;
}

AcWing 896. 最长上升子序列 II

用二分法来查找那个最大的小于a[i]的数，然后用它来覆盖他之后的那一个长度的最小值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
int a[N];
int q[N];

int main()
{
    cin >> n;

    for (int i = 0; i < n; i ++ ) 
        cin >> a[i];
    int len = 0;
    for (int i = 0; i < n; i ++ )
    {
       int l = 0, r = len;
       while( l < r)
       {
         int mid = (l + r + 1) >> 1;
         if( q[mid] < a[i] )    //保证是最大小于a[i]的位置，并覆盖q[r+1]
            l = mid;
         else
            r = mid - 1;
       }
       len = max(len, r + 1);
       q[r + 1] = a[i];
    }

    printf("%d\n", len);

    return 0;
}


AcWing 897. 最长公共子序列

如果字母相同，则可以取f[i][j] = f[i - 1][j - 1] + 1;，若不同，由于我们前面序列是确定的（即最长公共子序列），可以确保第i，j时，最长子序列的长度不变,即f[i][j] = max(f[i - 1][j], f[i][j - 1]);，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
char a[N], b[N];
int f[N][N];
int main() {
  cin >> n >> m >> a + 1 >> b + 1;	//加号优先级大于>>
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) {
        if(a[i] == b[j])
            f[i][j] = f[i - 1][j - 1] + 1;
        else
            f[i][j] = max(f[i - 1][j], f[i][j - 1]);
    }
    cout << f[n][m] << endl;
}

AcWing 902. 最短编辑距离

AcWing 902. 最短编辑距离 - AcWing

1
2
3
4
5
6
7
8
9
10
11
1)删除操作：把a[i]删掉之后a[1~i]和b[1~j]匹配
            所以之前要先做到a[1~(i-1)]和b[1~j]匹配
            f[i-1][j] + 1
2)插入操作：插入之后a[i]与b[j]完全匹配，所以插入的就是b[j] 
            那填之前a[1~i]和b[1~(j-1)]匹配
            f[i][j-1] + 1 
3)替换操作：把a[i]改成b[j]之后想要a[1~i]与b[1~j]匹配 
            那么修改这一位之前，a[1~(i-1)]应该与b[1~(j-1)]匹配
            f[i-1][j-1] + 1
            但是如果本来a[i]与b[j]这一位上就相等，那么不用改，即
            f[i-1][j-1] + 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <algorithm>
#include <iostream>

using namespace std;

const int N = 1010;

int n, m;
char a[N], b[N];
int f[N][N];

int main() {
  scanf("%d%s", &n, a + 1);
  scanf("%d%s", &m, b + 1);
  for (int i = 0; i <= n; i++)      //将前i个字母转为空串
    f[i][0] = i;
  for (int i = 0; i <= m; i++)       //将前i个字母转为空串
    f[0][i] = i;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) {
      f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
      if (a[i] == b[j])
        f[i][j] = min(f[i][j], f[i - 1][j - 1]);
      else
        f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
    }
  cout << f[n][m] << endl;
}

Acwing899编辑距离

这里采用编辑最短距离的思路，但是这题要注意strlen()函数，由于我们输入的位置是arr+1，因此字符串的首地址不再是pos，而是pos+1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <string.h>

using namespace std;

const int N = 15, M = 1010;
int f[N][N], x;
char str[M][N], a[N];

int main() {
  int n;
  cin >> n;
  int m;
  cin >> m;
  for (int i = 0; i < n; i++)
    cin >> str[i] + 1;

  while (m--) {
    int x;
    cin >> a + 1 >> x;
    int cnt = 0;

    for (int pos = 0; pos < n; pos++) {
      int lenpos = strlen(str[pos] + 1);
      int lena = strlen(a + 1);
      for (int i = 0; i <= lenpos; i++)
        f[i][0] = i;
      for (int i = 1; i <= lena; i++)
        f[0][i] = i;
      for (int i = 1; i <= lenpos; i++)
        for (int j = 1; j <= lena; j++) {
          f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
          if (str[pos][i] == a[j])
            f[i][j] = min(f[i - 1][j - 1], f[i][j]);
          else
            f[i][j] = min(f[i - 1][j - 1] + 1, f[i][j]);
        }
      if (x >= f[lenpos][lena])
        cnt++;
    }
    cout << cnt << endl;
  }
}

​

区间DP

AcWing 282. 石子合并

这里是从每次合并二堆开始枚举，直到最后一次合并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>


using namespace std;

const int N = 310;
int n;
int s[N];
int f[N][N];


int main(){
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> s[i];
    for(int i = 1; i<= n; i ++) 
        s[i] += s[i - 1];       //前缀和
    for(int len = 2; len<=n; len++)     //每次合并长度
        for(int i = 1; i+ len - 1 <= n; i++)
        {
            int l = i;
            int r = i + len - 1;        //每次合并多少石子
            f[l][r] = 1e8;      //初始化为无穷大
            for(int k = l; k <= r; k++)
            {
                f[l][r] = min(f[l][r], f[l][k] +f[k+1][r] + s[r] - s[l - 1])
            ;}

        }
        cout << f[1][n] << endl;
        return 0;
}

AcWing 900. 整数划分

这里采用完全背包的方式，从1开始到n，由于我们一开始是用1枚举的，因此可以保证背包是满的。

//TODO

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>

using namespace std;

const int N = 1e3 + 7, mod = 1e9 + 7;

int f[N][N];

int main() {
    int n;
    cin >> n;

    for (int i = 0; i <= n; i ++) {
        f[i][0] = 1; // 容量为0时，前 i 个物品全不选也是一种方案
    }

    for (int i = 1; i <= n; i ++) {
        for (int j = 0; j <= n; j ++) {
            f[i][j] = f[i - 1][j] % mod; // 特殊 f[0][0] = 1
            if (j >= i) f[i][j] = (f[i - 1][j] + f[i][j - i]) % mod;    //当可以塞入时，尝试塞入
        }
    }

    cout << f[n][n] << endl;
}


AcWing 338. 计数问题

这题我感觉像是模拟+前缀和，分析xxxjyyy的各种情况

AcWing 338. 计数问题<超短写法> - AcWing

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

#include <algorithm>
#include <cmath>
#include <iostream>
#include <utility>

using namespace std;

int get(int x) {
  int res = 0;
  while (x)
    res++, x /= 10;
  return res;
}

int count(int n, int i) {
  int res = 0, dgt = get(n);
  for (int j = 1; j <= dgt; ++j) {
    // p为当前遍历位次数大小
    // l为第j位的左边的数
    // r为右边的数
    // dj为第j位上的数
    int p = pow(10, dgt - j);
    int l = n/p/10;
    int r = n % p;
    int dj = n / p % 10;

    if(i)   res+=  l*p;         
    else    res+= (l - 1) * p;  //去除00...0的情况

    if (i == dj)     res += r + 1;      //等于需小于等于r
    if (i < dj)             res += p;   //小于可取全部值
    //大于则无

  }
  return res;
}

int main() {
  int a, b;
  while (cin >> a >> b, a) { // 输入处理，直到输入为0 0停止
    if (a > b)
      swap(a, b);
    for (int i = 0; i <= 9; ++i)
      cout << count(b, i) - count(a - 1, i) << ' ';
    //输出各位数字的个数
    //利用前缀和思想：[l,r]的和=s[r] - s[l - 1]
    cout << endl;
  }

  return 0;
}

状态压缩DP

AcWing 291. 蒙德里安的梦想

摆放的小方格方案数 等价于 横着摆放的小方格方案数

当我们确定唯一的横放小方格数量时，竖着放的小方格位置就已经确定了

  • 连续空着的列需要是偶数个
  • 该位置未被其他横放小方块占据

//TODO

AcWing 91. 最短Hamilton路径

AcWing 91. 最短Hamilton路径(超详解) - AcWing

//TODO

f[i][j]=min(f[i][j],f[i-(1<<j)][k]+w[k][j])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 20, M = 1 << N;

int f[M][N], w[N][N]; // w表示的是无权图

int main() {
  int n;
  cin >> n;

  for (int i = 0; i < n; i++)         
    for (int j = 0; j < n; j++)
      cin >> w[i][j];
  memset(f, 0x3f, sizeof(f));       
  f[1][0] = 0;      //000.。。1    的状态，初始化为0
  for (int i = 0; i < (1 << n); i++)          //枚举所有状态
    for (int j = 0; j < n; j++)     //枚举所有点
      if (i >> j & 1)       //判断j位是否为1，为1
        for (int k = 0; k < n; k++)     //k表示走到j这个点之前,以k为终点的最短距离
          if (i - (1 << j) >> k & 1)
            f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);

  cout << f[(1 << n) - 1][n - 1] << endl;
  // 11111111的情况   
}

AcWing 285. 没有上司的舞会

我们可以设置一个节点的状态为选中或未选中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 6010;

int n;
int h[N], e[N], ne[N], idx;
int happy[N];
int f[N][2];
bool has_fa[N]; //判断当前节点是否有父节点

void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}

void dfs(int u){
    f[u][1] = happy[u]; //节点u的快乐值，不选节点u为0，全局变量设置
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        dfs(j);
        f[u][1] += f[j][0];     //选父节点则不选子节点
        f[u][0] += max(f[j][0], f[j][1]);   //不选父节点，则选择子节点的最大快乐值
    }
}


int main()
{
    scanf("%d", &n);

    for (int i = 1; i <= n; i ++ ) scanf("%d", &happy[i]);

    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(b, a);      //反向建边，从根节点到叶子节点
        has_fa[a] = true;
    }
    int root = 1;
    while(has_fa[root]) //找到根节点
        root ++;
    dfs(root);
    printf("%d\n", max(f[root][0], f[root][1]))

}

AcWing 901. 滑雪

f[i][j]表示从该点出发可以达到的最大位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 310;
int n,m; 
int f[N][N]; 
int h[N][N];
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};


int dp(int x, int y){
    int &v = f[x][y];
      if(v != -1) return v; 
        v = 1; //注意v要先赋值为1哦~
    for(int i = 0;i < 4;i ++){ //四个方向
        int xx = x + dx[i];
        int yy = y + dy[i];
        if(xx >= 1 && xx <= n && yy >= 1 && yy <= m && h[x][y] > h[xx][yy]){ //判断这点是否能走
            v = max(v,dp(xx,yy) + 1); //更新
        }
    }
    return v; 
}

int main(){
    cin>>n>>m;
    for(int i = 1;i <= n;i ++){
        for(int j = 1;j <= m;j ++){
            cin>>h[i][j]; 
        }
    }
    memset(f,-1,sizeof f);  //初始化
    int res = 0;
    for(int i = 1;i <= n;i ++){
        for(int j = 1;j <= m;j ++){
           
            res = max(res,dp(i,j)); 
        }
    }
    cout<<res<<endl;
    return 0;
}