背包问题

背包问题 每个物品数量 状态转移函数
01背包 1 f(i,j)=max(f(i−1,j),f(i−1,j−v)+w)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)f(i, j) = max(f(i -1, j), f(i, j - v) + w)
多重背包 sis_i 把物品i打包成logsilogs_i个物品, 转化为01背包
分组背包 每组里只能选1个 f(i,j)=max(f(i−1,j−v(i,k))+w(i,k)),k=0,..,sif(i, j) = max(f(i - 1, j - v(i, k)) + w(i, k)), k = 0,..,s_i

阎式DP法：

  • 状态表示f[i][j]

    • 集合

      • 只从前i个物品中去选，且总体积不超过j的所有选项
      • 属性 Max, Min, Num

  • 状态计算

    • 集合划分

AcWing 2. 01背包问题

难度：简单

有 NN 件物品和一个容量是 VV 的背包。每件物品只能使用一次。

第 ii 件物品的体积是 viv_i，价值是 wiw_i。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式

第一行两个整数，N，VN，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 NN 行，每行两个整数 vi,wiv_i, w_i，用空格隔开，分别表示第 ii 件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

0<N,V≤10000 \lt N, V \le 1000
0<vi,wi≤10000\lt v_i, w_i \le 1000

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例：

8

二维dp数组

  • 状态计算 f[i][j] = max(f[i - 1][j], f[i- 1][j - v[i]] + w[i])
    • 以是否包含物品i进行分类
    • 不含i f[i - 1][j]
    • 含i f[i- 1][j - v[i]] + w[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
#include <iostream>
#include <algorithm>  // max()需要

using namespace std;

const int kN = 1010;
int n, m, v[kN], w[kN];
int f[kN][kN];

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d%d", &v[i], &w[i]);
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= m; j++) {
      f[i][j] = f[i - 1][j];
      if (j >= v[i]) {
        f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
      }
    }
  }
  printf("%d\n", f[n][m]);
  return 0;
}

代码层优化：一维dp数组

DP的优化很多是在代码层面的，而非算法层面。

f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]) 计算时只用到了上一层的信息，可用滚动数组优化。

由于f[i - 1][j - v[i]]使用到的是i - 1层信息，所以体积必须从大到小遍历。

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

using namespace std;

const int kN = 1010;
int n, m, v[kN], w[kN];
int f[kN];

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d%d", &v[i], &w[i]);
  }
  for (int i = 1; i <= n; i++) {
    for (int j = m; j >= v[i]; j--) {  // 不要到0
      f[j] = max(f[j], f[j - v[i]] + w[i]);
    }
  }
  printf("%d\n", f[m]);
  return 0;
}

AcWing 3. 完全背包问题

难度：简单

有 NN 种物品和一个容量是 VV 的背包，每种物品都有无限件可用。

第 ii 种物品的体积是 viv_i，价值是 wiw_i。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式

第一行两个整数，N，VN，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 NN 行，每行两个整数 vi,wiv_i, w_i，用空格隔开，分别表示第 ii 种物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

0<N,V≤10000 \lt N, V \le 1000
0<vi,wi≤10000 \lt v_i, w_i \le 1000

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例：

10

二维dp数组

  • 状态计算 f[i][j] = max(f[i - 1][j], f[i][j - v[i] + w[i])

    • 按照物品i选择多次进行分类

    • 物品i选k次 f[i - 1][j - k*v[i]] + k*w[i], k = 0,1,.. 

      1
      2
      3
      4
      5
      由于
      f[i][j] = max(f[i-1][j], f[i-1][j-v]+w, f[i-1][j-2v]+2w, ...)
      f[i][j-v] = max(         f[i-1][j-v],   f[i-1][j-2v]+2w, ...)
      所以 f[i][j] = max(f[i-1][j], f[i][j-v] + w) 
      ！与0-1背包问题不同的是 f[i-1][j-v]和f[i][j-v]

代码如下：

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 kN = 1010;
int n, m, v[kN], w[kN];
int f[kN][kN];

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d%d", &v[i], &w[i]);
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= m; j++) {
      f[i][j] = f[i - 1][j];
      if (j >= v[i]) {
        f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
      }
    }
  }
  printf("%d\n", f[n][m]);
  return 0;
}

一维度dp数组

由于f[i][j - v[i]]使用到的是i 层信息，所以体积必须从小到大遍历。

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

using namespace std;

const int kN = 1010;
int n, m, v[kN], w[kN];
int f[kN];

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d%d", &v[i], &w[i]);
  }
  for (int i = 1; i <= n; i++) {
    for (int j = v[i]; j <= m; j++) {  // 不要从0开始
      f[j] = max(f[j], f[j - v[i]] + w[i]);
    }
  }
  printf("%d\n", f[m]);
  return 0;
}

AcWing 4. 多重背包问题 I

难度：简单

有 NN 种物品和一个容量是 VV 的背包。

第 ii 种物品最多有 s_is\_i 件，每件体积是 v_iv\_i，价值是 w_iw\_i。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

输入格式

第一行两个整数，N，VN，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 NN 行，每行三个整数 v_i,w_i,s_iv\_i, w\_i, s\_i，用空格隔开，分别表示第 ii 种物品的体积、价值和数量。

输出格式

输出一个整数，表示最大价值。

数据范围

0<N,V≤1000 \lt N, V \le 100
0<v_i,w_i,s_i≤1000 \lt v\_i, w\_i, s\_i \le 100

输入样例

4 5
1 2 3
2 4 1
3 4 3
4 5 2

输出样例：

10

二维dp数组

  • 状态计算 f[i][j] = max(f[i - 1][j], f[i][j - v[i] + w[i])

    • 按照物品i选择多次进行分类

    • 物品i选k次 f[i - 1][j - k*v[i]] + k*w[i], k = 0,1,.. s[i]

    • 由于max的计算特性，无法像完全背包问题一样进行优化

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

using namespace std;

const int kN = 110;
int n, m, v[kN], w[kN], s[kN];
int f[kN][kN];

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d%d%d", &v[i], &w[i], &s[i]);
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= m; j++) {
      for (int k = 0; k <= s[i] && k * v[i] <= j; k++) {
        f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
      }
    }
  }
  printf("%d\n", f[n][m]);
  return 0;
}

一维dp数组

f[i - 1][j - k * v[i]]仅用到i - 1层信息，可用一维dp数组优化，注意体积从大到小循环。

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

using namespace std;

const int kN = 110;
int n, m, v[kN], w[kN], s[kN];
int f[kN];

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d%d%d", &v[i], &w[i], &s[i]);
  }
  for (int i = 1; i <= n; i++) {
    for (int j = m; j >= 0; j--) {  // 体积从大到小循环
      for (int k = 0; k <= s[i] && k * v[i] <= j; k++) {
        f[j] = max(f[j], f[j - k * v[i]] + k * w[i]);
      }
    }
  }
  printf("%d\n", f[m]);
  return 0;
}

AcWing 5. 多重背包问题 II

难度：中等

题目描述及输入输出与上题一致。

数据范围：

  • 0<N≤10000 < N ≤ 1000
  • 0<V≤20000 < V ≤ 2000
  • 0<vi,wi,si≤20000 < vi,wi,si ≤ 2000

二进制优化

若和上题一样不进行二进制优化，则时间复杂度为O(NVsi)O(NVs_i)，会到4×1094\times 10^9，而C++每秒大概算10810^8次，所以会超时。

使用二进制优化，时间复杂度变为O(NVlogsi)O(NVlog_{s_i}), 大概为2.2×1072.2\times 10^7次，不会超时。

二进制优化后转化为01背包，使用一维dp数组代码如下：

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
#include <iostream>
#include <algorithm>

using namespace std;

const int kN = 1000 * 11, kM = 2010;
int n, m, v[kN], w[kN], cnt;
int f[kM];

int main() {
  scanf("%d%d", &n, &m);
  int a, b, s;
  for (int i = 1; i <= n; i++) {
    scanf("%d%d%d", &a, &b, &s);
    int k = 1;
    while (k <= s) {
      cnt++;
      v[cnt] = k * a;
      w[cnt] = k * b;
      s -= k;
      k *= 2;
    }
    if (s > 0) {
      cnt++;
      v[cnt] = s * a;
      w[cnt] = s * b;
    }
  }
  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]);
    }
  }
  printf("%d\n", f[m]);
  return 0;
}

AcWing 9. 分组背包问题

难度：中等

有 NN 组物品和一个容量是 VV 的背包。

每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 v_ijv\_{ij}，价值是 w_ijw\_{ij}，其中 ii 是组号，jj 是组内编号。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

输出最大价值。

输入格式

第一行有两个整数 N，VN，V，用空格隔开，分别表示物品组数和背包容量。

接下来有 NN 组数据：

  • 每组数据第一行有一个整数 S_iS\_i，表示第 ii 个物品组的物品数量；
  • 每组数据接下来有 S_iS\_i 行，每行有两个整数 v_ij,w_ijv\_{ij}, w\_{ij}，用空格隔开，分别表示第 ii 个物品组的第 jj 个物品的体积和价值；

输出格式

输出一个整数，表示最大价值。

数据范围

0<N,V≤1000 \lt N, V \le 100
0<S_i≤1000 \lt S\_i \le 100
0<v_ij,w_ij≤1000 \lt v\_{ij}, w\_{ij} \le 100

输入样例

3 5
2
1 2
2 4
1
3 4
1
4 5

输出样例：

8

一维dp数组

  • 状态计算 f[i][j] = f[i - 1][j - v[i][k]] + w[i][k]
    • 按照i组物品选不选、选第几个进行分类
    • 不选 f[i - 1][j]
    • 选第k个 f[i - 1][j - v[i][k]] + w[i][k], k = 1,2,..,si

使用i-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
#include <iostream>
#include <algorithm>

using namespace std;

const int kN = 110, kM = 110;
int n, m, s[kN], v[kN][kM], w[kN][kM];
int f[kN];

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &s[i]);
    for (int k = 1; k <= s[i]; k++) {
      scanf("%d%d", &v[i][k], &w[i][k]);
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = m; j >= 0; j--) {
      for (int k = 1; k <= s[i]; k++) {
        if (j >= v[i][k]) {
          // 最开始的f[j]就是f[i - 1][j], 即包含不选第i组物品的情况
          f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
        }
      }
    }
  }
  printf("%d\n", f[m]);
  return 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
#include <iostream>
#include <algorithm>

using namespace std;

const int kM = 110;
int n, m, v[kM], w[kM];
int f[kM];

int main() {
  scanf("%d%d", &n, &m);
  int s;
  while (n--) {
    scanf("%d", &s);
    for (int k = 1; k <= s; k++) {
      scanf("%d%d", &v[k], &w[k]);
    }
    for (int j = m; j >= 0; j--) {
      for (int k = 1; k <= s; k++) {
        if (j >= v[k]) {  // 一定要记得判断喔
          f[j] = max(f[j], f[j - v[k]] + w[k]);
        }
      }
    }
  }
  printf("%d\n", f[m]);
  return 0;
}

线性DP

AcWing 898. 数字三角形

难度：简单

给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

输入格式

第一行包含整数 nn，表示数字三角形的层数。

接下来 nn 行，每行包含若干整数，其中第 ii 行表示数字三角形第 ii 层包含的整数。

输出格式

输出一个整数，表示最大的路径数字和。

数据范围

1≤n≤5001 \le n \le 500,
\-10000 \le 三角形中的整数 \le 10000

输入样例：

5
7
3 8
8 1 0 
2 7 4 4
4 5 2 6 5

输出样例：

30

算法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
#include <iostream>
#include <algorithm>

using namespace std;

const int kN = 510, kINF = 1e9;
int n, a[kN][kN], f[kN][kN];

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,0], f[i,i+1]
          f[i][j] = -kINF;
      }
  }

  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], f[i - 1][j]) + a[i][j];
      }
  }

  int res = -kINF;
  for (int i = 1; i <= n; i++) {
      if (f[n][i] > res) {
          res = f[n][i];
      }
  }
  printf("%d\n", res);
  return 0;
}

算法2 自底向上动态规划

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

using namespace std;

const int kN = 510;
int n, f[kN][kN];

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= i; j++) {
          scanf("%d", &f[i][j]);
      }
  }
  for (int i = n; i >= 1; i--) {
      for (int j = i; j >= 1; j--) {
          f[i][j] = max(f[i + 1][j], f[i + 1][j + 1]) + f[i][j];
      }
  }
  printf("%d\n", f[1][1]);
  return 0;
}

AcWing 895. 最长上升子序列

难度：简单

给定一个长度为 NN 的数列，求数值严格单调递增的子序列的长度最长是多少。

输入格式

第一行包含整数 NN。

第二行包含 NN 个整数，表示完整序列。

输出格式

输出一个整数，表示最大长度。

数据范围

1≤N≤10001 \le N \le 1000，
−109≤数列中的数≤109-10^9 \le 数列中的数 \le 10^9

输入样例：

7
3 1 2 1 8 5 6

输出样例：

4

DP

  • 状态表示f[i]
    • 集合：所有以第i个数结尾的上升子序列
    • 属性：MAX(序列最大长度)
  • 状态计算
    • 以倒数第2个数在一位进行分类
    • f[i] = max(f[j] + 1), a[j] < a[i], j = 0,1,...,i-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
#include <iostream>
#include <algorithm>

using namespace std;

const int kN = 1010;
int n, a[kN], f[kN];

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
      scanf("%d", &a[i]);
  }
  for (int i = 1; i <= n; i++) {
      f[i] = 1;
      for (int j = 0; i < i; j++) {
          if (a[j] < a[i]) {
              f[i] = max(f[i], f[j] + 1);
          }
      }
  }
  int res = 1;
  for (int i = 1; i <= n; i++) {
      if (res > f[i]) {
          res = f[i];
      }
  }
  printf("%d\n", res);
  return 0;
}

AcWing 896. 最长上升子序列 II

给定一个长度为 NN 的数列，求数值严格单调递增的子序列的长度最长是多少。

输入格式

第一行包含整数 NN。

第二行包含 NN 个整数，表示完整序列。

输出格式

输出一个整数，表示最大长度。

数据范围

1≤N≤1000001 \le N \le 100000，
\-10^9 \le 数列中的数 \le 10^9

输入样例：

7
3 1 2 1 8 5 6

输出样例：

4

贪心法

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 <algorithm>

using namespace std;

const int kN = 1e5 + 10;
int n, a[kN];
int q[kN]; // q[i]存放长度为i的递增序列的最后一位, q数组递增

int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
  }
  int len = 0; // 当前已确定的最长递增序列长度
  // 二分法查找q数组中比a[i]小的最大元素
  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]) l = mid;
      else r = mid - 1;
    }
    len = max(len, r + 1);
    q[r + 1] = a[i];
  }
  printf("%d\n", len);
  return 0;
}

AcWing 897. 最长公共子序列

难度：简单

给定两个长度分别为 NN 和 MM 的字符串 AA 和 BB，求既是 AA 的子序列又是 BB 的子序列的字符串长度最长是多少。

输入格式

第一行包含两个整数 NN 和 MM。

第二行包含一个长度为 NN 的字符串，表示字符串 AA。

第三行包含一个长度为 MM 的字符串，表示字符串 BB。

字符串均由小写字母构成。

输出格式

输出一个整数，表示最大长度。

数据范围

1≤N,M≤10001 \le N,M \le 1000

输入样例：

4 5
acbd
abedc

输出样例：

3

DP

  • 状态表示f[i][j]
    • 集合：所有在第一个序列的前i个字母出现，且在第二个序列的前j个字母中出现的自序列
    • 属性：Max(序列的最大长度)
  • 状态计算
    • 以a[i],b[j]是否为序列的一员进行分类(00, 01, 10, 11)
    • 00 对应 f[i -1][j - 1]
    • 01 对应的子序列 包含于f[i - 1, j]对应子序列 包含于 f[i, j]对应子序列
      • 这样f[i - 1][j]在求Max的过程中一定会包含01且不会超出f[i][j]对应的Max
      • 00 对应的情况不需要写出来，因为f[i - 1][j - 1]对应子序列一定包含于f[i - 1][j]对应的子序列中
      • 求Max问题可以有重复
    • 10 同理
    • 11 对应f[i - 1][j - 1] + 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <algorithm>

using namespace std;

const int kN = 1010;
int n, m;
char a[kN], b[kN];
int f[kN][kN];

int main() {
  scanf("%d%d", &n, &m);
  scanf("%s%s", a + 1, b + 1);  // 字符串不需要取地址符, 从下标为1的位置开始读
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      f[i][j] = max(f[i - 1][j], f[i][j - 1]);
      if (a[i] == b[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
    }
  }
  printf("%d\n", f[n][m]);
  return 0;
}

AcWing 902. 最短编辑距离

难度：简单

给定两个字符串 AA 和 BB，现在要将 AA 经过若干操作变为 BB，可进行的操作有：

  1. 删除–将字符串 AA 中的某个字符删除。
  2. 插入–在字符串 AA 的某个位置插入某个字符。
  3. 替换–将字符串 AA 中的某个字符替换为另一个字符。

现在请你求出，将 AA 变为 BB 至少需要进行多少次操作。

输入格式

第一行包含整数 nn，表示字符串 AA 的长度。

第二行包含一个长度为 nn 的字符串 AA。

第三行包含整数 mm，表示字符串 BB 的长度。

第四行包含一个长度为 mm 的字符串 BB。

字符串中均只包含大小写字母。

输出格式

输出一个整数，表示最少操作次数。

数据范围

1≤n,m≤10001 \le n, m \le 1000

输入样例：

10 
AGTCTGACGC
11 
AGTAAGTAGGC

输出样例：

4

DP

  • 状态表示f[i][j]
    • 集合：所有将a[1~i]变成b[1~j]的操作方式
    • 属性：Min
  • 状态计算
    • 以最后一步进行的操作进行分类
    • 删除 f[i - 1][j]
    • 插入 f[i][j - 1]
    • 替换 f[i - 1][j - 1] + 0/1 如果a[i] = b[j]则加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
#include <iostream>
#include <algorithm>

using namespace std;

const int kN = 1010;
int n, m;
char a[kN], b[kN];
int f[kN][kN];

int main() {
  scanf("%d%s", &n, a + 1);
  scanf("%d%s", &m, b + 1);
  // 初始化
  // f[0][i]如果a初始长度就是0，那么只能用插入操作让它变成b
  // f[i][0]同样地，如果b的长度是0，那么a只能用删除操作让它变成b
  for (int i = 1; i <= m; i++) {
    f[0][i] = i;
  }
  for (int i = 1; i <= n; i++) {
    f[i][0] = 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);  // 删除 添加
      f[i][j] = min(f[i][j], f[i - 1][j - 1] + (a[i] != b[j]));
    }
  }
  printf("%d\n", f[n][m]);
  return 0;
}

AcWing 899. 编辑距离

难度：简单

给定 nn 个长度不超过 1010 的字符串以及 mm 次询问，每次询问给出一个字符串和一个操作次数上限。

对于每次询问，请你求出给定的 nn 个字符串中有多少个字符串可以在上限操作次数内经过操作变成询问给出的字符串。

每个对字符串进行的单个字符的插入、删除或替换算作一次操作。

输入格式

第一行包含两个整数 nn 和 mm。

接下来 nn 行，每行包含一个字符串，表示给定的字符串。

再接下来 mm 行，每行包含一个字符串和一个整数，表示一次询问。

字符串中只包含小写字母，且长度均不超过 1010。

输出格式

输出共 mm 行，每行输出一个整数作为结果，表示一次询问中满足条件的字符串个数。

数据范围

1≤n,m≤10001 \le n, m \le 1000,

输入样例：

3 2
abc
acd
bcd
ab 1
acbd 2

输出样例：

1
3

DP

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
#include <iostream>
#include <algorithm>
#include <string.h>

using namespace std;

const int kN = 1010, kM = 15;
int n, m;
char str[kN][kM];
int f[kM][kM];

int EditDist(char a[], char b[]) {  // 传的就是指针
  // 一定要从a + 1开始读长度(从a开始读长度读出来是0: 读到\00为止)
  int len_a = strlen(a + 1), len_b = strlen(b + 1);
  for (int i = 1; i <= len_b; i++) {
    f[0][i] = i;
  }
  for (int i = 1; i <= len_a; i++) {
    f[i][0] = i;
  }
  for (int i = 1; i <= len_a; i++) {
    for (int j = 1; j <= len_b; j++) {
      f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
      f[i][j] = min(f[i][j], f[i - 1][j - 1] + (a[i] != b[j]));
    }
  }
  return f[len_a][len_b];
}

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) {
    scanf("%s", str[i] + 1);
  }
  char str_query[kM];
  int limit;
  while (m--) {
    scanf("%s%d", str_query + 1, &limit);
    int count = 0;
    for (int i = 0; i < n; i++) {
      if (EditDist(str[i], str_query) <= limit) {
        count++;
      }
    }
    printf("%d\n", count);
  }
  return 0;
}

区间DP

AcWing 282. 石子合并

难度：简单

设有 NN 堆石子排成一排，其编号为 1，2，3，…，N1，2，3，…，N。

每堆石子有一定的质量，可以用一个整数来描述，现在要将这 NN 堆石子合并成为一堆。

每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。

例如有 44 堆石子分别为 1 3 5 2， 我们可以先合并 1、21、2 堆，代价为 44，得到 4 5 2， 又合并 1，21，2 堆，代价为 99，得到 9 2 ，再合并得到 1111，总代价为 4+9+11=244+9+11=24；

如果第二步是先合并 2，32，3 堆，则代价为 77，得到 4 7，最后一次合并代价为 1111，总代价为 4+7+11=224+7+11=22。

问题是：找出一种合理的方法，使总的代价最小，输出最小代价。

输入格式

第一行一个数 NN 表示石子的堆数 NN。

第二行 NN 个数，表示每堆石子的质量(均不超过 10001000)。

输出格式

输出一个整数，表示最小代价。

数据范围

1≤N≤3001 \le N \le 300

输入样例：

4
1 3 5 2

输出样例：

22

区间DP

区间DP：定义状态时定义的是一个空间。

  • 状态表示f[i][j]

    • 集合：所有将第i堆石子到第j堆石子合并成一堆石子的合并方式。
    • 属性：Min

  • 状态计算

    • 以最后一次分界线的位置来分类

    • 分界线k可以确定[i，k]和[k+1，r]两个区间
      f[i][j] = min(f[i][k] + f[k+1][j] + s[k] - s[i-1]), k=i~j-1

      注意：右边界的起点是k+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
#include <iostream>
#include <algorithm>

using namespace std;

const int kN = 310;
int n, s[kN];z
int f[kN][kN];

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &s[i]);
    s[i] += s[i - 1];  // 前缀和
  }
  // 考虑如何使得在计算后面的状态时, 前面的状态已被计算: 外循环枚举len
  for (int len = 2; len <= n; len++) {
    for (int i = 1; i + len - 1 <= n; i++) {
      int l = i, r = i + len - 1;
      f[l][r] = 2e9;
      for (int k = l; k < r; k++) {  // k枚举左半部分最后一个石子的位置
        f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
      }
    }
  }
  printf("%d\n", f[1][n]);
  return 0;
}

计数类DP

AcWing 900. 整数划分

一个正整数 nn 可以表示成若干个正整数之和，形如：n=n_1+n_2+…+n_kn = n\_1 + n\_2 + … + n\_k，其中 n_1≥n_2≥…≥n_k,k≥1n\_1 \ge n\_2 \ge … \ge n\_k, k \ge 1。

我们将这样的一种表示称为正整数 nn 的一种划分。

现在给定一个正整数 nn，请你求出 nn 共有多少种不同的划分方法。

输入格式

共一行，包含一个整数 nn。

输出格式

共一行，包含一个整数，表示总划分数量。

由于答案可能很大，输出结果请对 109+710^9 + 7 取模。

数据范围

1≤n≤10001 \le n \le 1000

输入样例:

5

输出样例：

7

算法1 完全背包解法(推荐)

转化为完全背包问题：从1 ~ n 这些数去选，可以选任意多个，使得总和恰好为n

  • 状态表示f[i][j]

    • 集合 只从1～i 中选，总和恰好等于j的方案
    • 属性 Num

  • 状态计算 f[i][j] = f[i - 1][j] + f[i][j - i]

    • 按照i选几个进行划分

    • 选择k个i f[i - 1][j - k*i]

      1
      2
      3
      4
      5
      6
      7
      因为
      f[i][j] = f[i-1][j] + f[i-1][j-i] + f[i-1][j-2i] +...+ f[i-1][j-si]
      f[i][j-i] =           f[i-1][j-i] + f[i-1][j-2i] +...+ f[i-1][j-si]
      所以
      f[i][j] = f[i - 1][j] + f[i][j - i]
      一维优化
      f[j] = f[j] + f[j - i], j从小到大循环

代码如下：

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

using namespace std;

const int kN = 1010, kMOD = 1e9 + 7;
int n;
int f[kN];

int main() {
  scanf("%d", &n);
  f[0] = 1;  // 初始化,选择0个数使得体积为0有1种情况
  for (int i = 1; i <= n; i++) {
    for (int j = i; j <= n; j++) {
      f[j] = (f[j] + f[j - i]) % kMOD;
    }
  }
  printf("%d\n", f[n]);
  return 0;
}

算法2

  • 状态表示f[i][j]
    • 集合：总和为 i , 总个数为 j 的方案
    • 属性：Num
  • 状态计算
    • 按划分结果中最小值是否为1进行分类
    • 最小值为1 f[i - 1][j - 1]
    • 最小值非1 f[i - j][j], 即这j个划分中每一部分都可以提取出一个1出来
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <algorithm>

using namespace std;

const int kN = 1010, kMOD = 1e9 + 7;
int n, f[kN][kN];

int main() {
  scanf("%d", &n);
  f[1][1] = 1;
  for (int i = 2; i <= n; i++) {
    for (int j = 1; j <= i; j++) {
      f[i][j] = max(f[i][j], f[i - 1][j - 1] + f[i - j][j]) % kMOD;  // 取模
    }
  }
  int res = 0;
  for (int i = 1; i <= n; i++) {
    res = (res + f[n][i]) % kMOD;  // 结果是 各自划分个数 的方案数之和
  }
  printf("%d\n", res);
  return 0;
}

数位统计DP

AcWing 338. 计数问题

给定两个整数 aa 和 bb，求 aa 和 bb 之间的所有数字中 0∼90 \sim 9 的出现次数。

例如，a=1024，b=1032a=1024，b=1032，则 aa 和 bb 之间共有 99 个数如下：

1024 1025 1026 1027 1028 1029 1030 1031 1032

其中 0 出现 1010 次，1 出现 1010 次，2 出现 77 次，3 出现 33 次等等…

输入格式

输入包含多组测试数据。

每组测试数据占一行，包含两个整数 aa 和 bb。

当读入一行为 0 0 时，表示输入终止，且该行不作处理。

输出格式

每组数据输出一个结果，每个结果占一行。

每个结果包含十个用空格隔开的数字，第一个数字表示 0 出现的次数，第二个数字表示 1 出现的次数，以此类推。

数据范围

0<a,b<1000000000 < a,b < 100000000

输入样例：

1 10
44 497
346 542
1199 1748
1496 1403
1004 503
1714 190
1317 854
1976 494
1001 1960
0 0

输出样例：

1 2 1 1 1 1 1 1 1 1
85 185 185 185 190 96 96 96 95 93
40 40 40 93 136 82 40 40 40 40
115 666 215 215 214 205 205 154 105 106
16 113 19 20 114 20 20 19 19 16
107 105 100 101 101 197 200 200 200 200
413 1133 503 503 503 502 502 417 402 412
196 512 186 104 87 93 97 97 142 196
398 1375 398 398 405 499 499 495 488 471
294 1256 296 296 296 296 287 286 286 247

计数问题硬上法

此题不给出数位DP解法：感觉不如硬上直接、简单
数位DP解法可参考：用提高课的方式打开基础课acwing338计数问题

技巧1 [L, R] -> f(L, i) - f(R - 1， i), f(n, i)为求1～n数字i个数的函数

技巧2 f(n, i) -> f(∑xxx<dj>yyy, i)f(\sum xxx<dj>yyy,\ i), 即问题转化为求数字1～n的第j位上的数字i个数
<leftPart><dj><rightPart>是n的十进制展开，xxx和yyy都不特指3位数，其位数应当分别与<leftPart>和<rightPart>对应，dj是展开数中第j位的数字

技巧3 按xxx大分类讨论：求xxx<dy>yyy形式的数中，数字i在第j位的出现次数

  1. xxx < <leftPart>

    1. 若i不为0，xxx可取000 ~ <leftPart> - 1，有<leftPart> * p种，p = pow(10, j)

    2. 若i等于0，xxx可取001 ~ <leftPart> - 1，有(<leftPart> - 1) * p种

      当i = 0时，当<dj> = 0时，xxx不能为0（不能有前导0，否则11也能按0011算，给0加数量）

  2. xxx = <leftPart>

    1. i < dj时 yyy : 000 ~ 9…9 即p种选法
    2. i = dj时 yyy : 000 ~ <rightPart> 即<rightPart> + 1 种
    3. i > dj时 0种选法

  3. xxx > <leftPart> 超出范围

下面做法很重要的一个问题是else res += (left - 1) * p; 会在i = 0, left = 0时也会执行
但是由于if (dj > i) res += p也未判断i 和left是否同时为0（不能同时为0，同时为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
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <cmath>

using namespace std;

int getDigit(int n) {
  int res = 0;
  while (n) {
    res++;
    n /= 10;
  }
  return res;
}

int count(int n, int i) {
  // 不要把求n的位数, 求第j位数字都放在一个函数中: 求n位数时会将n归零
  int res = 0, dgt = getDigit(n);
  for (int j = dgt - 1; ~j; j--) {  // ~j表示
    int p = pow(10, j);
    int left = n / p / 10, right = n % p, dj = n / p % 10;
    if (i) res += left * p;
    else res += (left - 1) * p;  
    if (dj > i) res += p;
    else if (dj == i) res += right + 1;  // 左边取xxx, dj=i时,右边可取000~right
  }
  return res;
}

int main() {
  int l, r;
  while (scanf("%d%d", &l, &r), l || r) {
    if (l > r) swap(l, r);
    for (int i = 0; i <= 9; i++) {
      printf("%d ", count(r, i) - count(l - 1, i));
    }
    printf("\n");
  }
}

状态压缩DP

状态压缩:用（二进制）整数表示一个状态。

AcWing 291. 蒙德里安的梦想

难度：中等

求把 N×MN \times M 的棋盘分割成若干个 1×21 \times 2 的长方形，有多少种方案。

例如当 N=2，M=4N=2，M=4 时，共有 55 种方案。当 N=2，M=3N=2，M=3 时，共有 33 种方案。

如下图所示：

image-20221125190249113

输入格式

输入包含多组测试用例。

每组测试用例占一行，包含两个整数 NN 和 MM。

当输入用例 N=0，M=0N=0，M=0 时，表示输入终止，且该用例无需处理。

输出格式

每个测试用例输出一个结果，每个结果占一行。

数据范围

1≤N,M≤111 \le N,M \le 11

输入样例：

1 2
1 3
1 4
2 2
2 3
2 4
2 11
4 11
0 0

输出样例：

1
0
1
2
3
5
144
51205

状态压缩dp + 预处理

思考：

  1. 先放横放方块，而后纵放小方块的方案唯一确定
    即：总方案数 = 只放横向小方块的数量
  2. 判断是否合法？
    按列看，1、连续两列同行小方块不冲突；2、每列内部所有连续空着的小方块需要是偶数个。

DP：

  • 状态表示f[i][j]

    • 集合 已将前i - 1列摆好，且从i - 1列伸到第i列的状态是j的方案
      j为一个二进制数，范围是0～n的二进制范围；
    • 属性 Num

  • 状态计算

    • 按照i - 1列的状态k进行分类

    • f[i - 1][k]需要满足

      1. (j & k) == 0 (同一行连续两列不能都放小方块)
      2. 所有连续空着位置的长度必须为偶数 st[j | k]

      考虑状态j可能由哪些状态k转移过来，这个k是第i-1层的问题

      第i-1列是否满足第2点要看两个状态：j和k
      j是在i-1层放置的小方块伸出来导致的，k是i-2列小方块伸出的

补充：

  • 列下标从0开始，最终状态f[m][0]
  • 预处理计算st和states时不能放在while循环外
    因为st是根据n的变化而变化的，以st[0]为例，st[0]表示的是状态为0时，是否有连续奇数个空格子，如果n=1那么棋盘总共只有1行，状态为0时只有1个连续空格，此时st[0]=false;如果n=2，则棋盘上有两行，状态为00，有两个空格子，所以st[0]=true
  • 初始化：f[0][0] = 1;
    第0列其实是不存在的，你可以认为它是为了后面DP公式能正确递推而创造出来的，同时它的摆法也不能插入到第1列影响后续的摆法，所以它的摆法只能是竖放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
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
56
57
#include <iostream>
#include <vector>
#include <cstring>  // memset()在C中在<string.h>，C++中在<cstring>

using namespace std;

const int kN = 12, kM = 1 << kN;

bool st[kM];  // st[j]: 在n行时, 状态j是否合法
vector<int> states[kM];  // states[j]: 哪些状态k可以转移到状态j
// vector<vector<int>> states(kN); 与上一句等价
long long f[kN][kM];

int main() {
  int n, m;
  while (scanf("%d%d", &n, &m), n || m) {
    // 预处理1: 对于每种状态，先预处理每列不能有奇数个连续的0
    for (int i = 0; i < (1 << n); i++) {
      st[i] = true;
      int cnt = 0;
      for (int j = 0; j < n; j++) {
        if (i >> j & 1) {
          if (cnt & 1) {
            // st[i] = false;
            break;
          }
          // cnt = 0;
        } else {
          cnt++;
        }
      }
      if (cnt & 1) st[i] = false;
    }
    
    // 预处理2: 求到状态j的所有合法状态
    for (int j = 0; j < (1 << n); j++) {
      states[j].clear();
      for (int k = 0; k < (1 << n); k++) {
        if ((j & k) == 0 && st[j | k]) {  // ==较&优先
          states[j].push_back(k);
        }
      }
    }
    
    memset(f, 0, sizeof f);
    f[0][0] = 1;  // ?
    for (int i = 1; i <= m; i++) {
      for (int j = 0; j < (1 << n); j++) {
        for (auto k: states[j]) {
          f[i][j] += f[i - 1][k];
        }
      }
    }
    printf("%lld\n", f[m][0]);  // 打印用%lld
  }
  return 0;
}

AcWing 91. 最短Hamilton路径

难度：中等

给定一张 nn 个点的带权无向图，点从 0∼n−10 \sim n-1 标号，求起点 00 到终点 n−1n-1 的最短 Hamilton 路径。

Hamilton 路径的定义是从 00 到 n−1n-1 不重不漏地经过每个点恰好一次。

输入格式

第一行输入整数 nn。

接下来 nn 行每行 nn 个整数，其中第 ii 行第 jj 个整数表示点 ii 到 jj 的距离（记为 a[i,j]a[i,j]）。

对于任意的 x,y,zx,y,z，数据保证 a[x,x]=0，a[x,y]=a[y,x]a[x,x]=0，a[x,y]=a[y,x] 并且 a[x,y]+a[y,z]≥a[x,z]a[x,y]+a[y,z] \ge a[x,z]。

输出格式

输出一个整数，表示最短 Hamilton 路径的长度。

数据范围

1≤n≤201 \le n \le 20
0≤a[i,j]≤1070 \le a[i,j] \le 10^7

输入样例：

5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0

输出样例：

18

状态压缩dp

  • 状态表示 f[i][j]
    • 集合 所有从0走到j,走过的点集是i的所有路径
    • 属性 Min
  • 状态计算 f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j])
    • 按照倒数第2步走那个点进行分类
    • 走k f[i - (1 << j)][k]
      从到j的集合点的集合i，除去j本身得到i - (1 << j)

初始化 f[1][0] = 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
30
31
32
33
34
35
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int kN = 20, kM = 1 << kN;  // kN不能开大了, 22就报MLE

int w[kN][kN], f[kM][kN];

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      scanf("%d", &w[i][j]);
    }
  }
  // 一定要初始化
  memset(f, 0x3f, sizeof f);
  f[1][0] = 0;
  for (int i = 0; i < (1 << n); i++) {
    for (int j = 0; j < n; j++) {
      if (i >> j & 1) {  // 经过j的状态才有意义
        for (int k = 0; k < n; k++) {  // k不一定小于j
          if ((i - (1 << j)) >> k & 1) {
            f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);
          }
        }
      }
    }
  }
  printf("%d\n", f[(1 << n) - 1][n - 1]);
  return 0;
}

树形DP

AcWing 285. 没有上司的舞会

难度：简单

Ural 大学有 NN 名职员，编号为 1∼N1 \sim N。

他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。

每个职员有一个快乐指数，用整数 H_iH\_i 给出，其中 1≤i≤N1 \le i \le N。

现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。

在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值。

输入格式

第一行一个整数 NN。

接下来 NN 行，第 ii 行表示 ii 号职员的快乐指数 H_iH\_i。

接下来 N−1N-1 行，每行输入一对整数 L,KL, K，表示 KK 是 LL 的直接上司。

输出格式

输出最大的快乐指数。

数据范围

1≤N≤60001 \le N \le 6000,
−128≤H_i≤127-128 \le H\_i \le 127

输入样例：

7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5

输出样例：

5

树形dp

  • 状态表示 f[u][0 / 1]
    • 集合 从所有以u为根节点的子树中选，且不选(0) / 选择(1) u的方案
    • 属性 Max
  • 状态计算
    • 不选u其子树根选不选都可以 f[u][0]=∑max(f[si][0],f[si][1])f[u][0] = \sum max(f[s_i][0], f[s_i][1])
    • 选了u其子树根一定不能选 f[u][1]=w[u]+∑max(f[si][0])f[u][1] = w[u] + \sum max(f[s_i][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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int kN = 6010;
int n;
int h[kN], e[kN], ne[kN], idx;
int happy[kN];
bool has_father[kN];
int f[kN][2];

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];
  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++) {  // 序号为1~n, 要和后面建边对应
    scanf("%d", &happy[i]);
  }
  memset(h, -1, sizeof h);  // 邻接表初始化
  while (--n) {
    int a, b;
    scanf("%d%d", &a, &b);
    add(b, a);  // b是上司
    has_father[a] = true;
  }
  int root = 1;
  while (has_father[root]) root++;
  dfs(root);
  printf("%d\n", max(f[root][0], f[root][1]));
  return 0;
}

记忆化搜索

记忆搜索是一种递归实现方式。
可以显著降低代码复杂度（好写），确定在于可能爆栈。

AcWing 901. 滑雪

难度：简单

给定一个 RR 行 CC 列的矩阵，表示一个矩形网格滑雪场。

矩阵中第 ii 行第 jj 列的点表示滑雪场的第 ii 行第 jj 列区域的高度。

一个人从滑雪场中的某个区域内出发，每次可以向上下左右任意一个方向滑动一个单位距离。

当然，一个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度。

下面给出一个矩阵作为例子：

 1  2  3  4 5

16 17 18 19 6

15 24 25 20 7

14 23 22 21 8

13 12 11 10 9

在给定矩阵中，一条可行的滑行轨迹为 24−17−2−124-17-2-1。

在给定矩阵中，最长的滑行轨迹为 25−24−23−…−3−2−125-24-23-…-3-2-1，沿途共经过 2525 个区域。

现在给定你一个二维矩阵表示滑雪场各区域的高度，请你找出在该滑雪场中能够完成的最长滑雪轨迹，并输出其长度(可经过最大区域数)。

输入格式

第一行包含两个整数 RR 和 CC。

接下来 RR 行，每行包含 CC 个整数，表示完整的二维矩阵。

输出格式

输出一个整数，表示可完成的最长滑雪长度。

数据范围

1≤R,C≤3001 \le R,C \le 300,
0≤矩阵中整数≤100000 \le 矩阵中整数 \le 10000

输入样例：

5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

输出样例：

25

记忆化搜索

  • 状态表示 f[i, j]
    • 集合 所有从(i, j)开始滑行的路径
    • 属性 Max
  • 状态计算
    • 按下一步滑行的方向进行分类
    • 如向右滑 f[i, j + 1] + 1
      注意是否合法：边界内 and 比当前点低
      要形成拓扑图，不能存在环形依赖
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
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

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

int n, m;
int g[kN][kN];
int f[kN][kN];

int dp(int x, int y) {
  int &v = f[x][y];  // 除了加速函数参数传递效率，也可以缩短代码长度
  if (v != -1) return v;
  v = 1;  // 初始化, 其本身就算一步
  for (int i = 0; i < 4; i++) {
    int a = x + dx[i], b = y + dy[i];
    if (a >= 0 && a < n && b >= 0 && b < m && g[a][b] < g[x][y])
      v = max(v, dp(a, b) + 1);
  }
  return v;
}

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      scanf("%d", &g[i][j]);
    }
  }
  memset(f, -1, sizeof f);  // 初始化, 所有状态未被计算
  int res = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      res = max(res, dp(i, j));
    }
  }
  printf("%d\n", res);
  return 0;
}