小旭讲解 基础算法系列 – 线性 DP 之 Sequence Matching

视频讲解

代码

// https://atcoder.jp/contests/abc185/tasks/abc185_e
#include<bits/stdc++.h>
using namespace std;
int main() {
    int n,m;
    cin>>n>>m;
    int a[n+1],b[m+1];
    for (int i=1;i<=n;++i) {
        cin>>a[i];
    }
    for (int i=1;i<=m;++i) {
        cin>>b[i];
    }
    int f[n+1][m+1];
    memset(f,0x3f,sizeof f);
    f[0][0] = 0;
    for (int i=0;i<=n;++i) {
        for (int j=0;j<=m;++j) {
            if (i == 0 || j == 0) {
                // f[0][1] = 1, f[3][0] = 3
                f[i][j] = max(i,j);
                continue;
            }
            // 删除 i
            f[i][j] = min(f[i][j], f[i-1][j]+1);
            // 删除 j
            f[i][j] = min(f[i][j], f[i][j-1]+1);
            // 保留 i 和 j
            f[i][j] = min(f[i][j], f[i-1][j-1] + ((a[i] != b[j]) ? 1 : 0));
        }
    }
    cout<<f[n][m]<<endl;
    return 0;
}

参考

[1]. AtCoder ABC 185 e Sequence Matching. https://atcoder.jp/contests/abc185/tasks/abc185_e

欢迎分享，引用。若转载，请联系我，谢谢配合。
本文地址：https://qoogle.top/xiaoxu-tutorial-bas-linear-dp-sequence-matching/