AtCoder ABC185E. Sequence Matching
原题链接
中等
算法
(DP) $O(nm)$
- 令
dp[i][j]
为 $A$ 的 前 $i$ 个字符,并且 $B$ 的前 $j$ 个字符的答案
- $dp[0][0] = 0$
- 删除 $A[0…i]$ 的末尾:$chmin(dp[i+1][j], dp[i][j] + 1)$
- 删除 $B[0…j]$ 的末尾:$chmin(dp[i][j+1], dp[i][j] + 1)$
- 考虑 $A[0…i]$ 的末尾和 $B[0…j]$ 的末尾匹配情况:
$$chmin(dp[i+1][j+1], dp[i][j] + (A[i] == B[j]))$$
- 这题和 编辑距离 很类似,不过本质都是 $LCS$ 问题。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using std::min;
const int INF = 1001001001;
template<typename T>
void chmin(T& a, const T& b) { a = min(a, b); }
int main() {
int n, m;
cin >> n >> m;
vector<int> a(n), b(m);
rep(i, n) cin >> a[i];
rep(i, m) cin >> b[i];
auto dp = vector(n + 1, vector(m + 1, INF));
dp[0][0] = 0;
rep(i, n + 1)rep(j, m + 1) {
// 删除A的末尾元素
if (i < n) chmin(dp[i + 1][j], dp[i][j] + 1);
// 删除B的末尾元素
if (j < m) chmin(dp[i][j + 1], dp[i][j] + 1);
// 将A的末尾和B的末尾匹配
if (i < n && j < m) {
int co = 0;
if (a[i] != b[j]) co = 1;
chmin(dp[i + 1][j + 1], dp[i][j] + co);
}
}
cout << dp[n][m] << '\n';
return 0;
}