---
title: "最长公共子序列"
created: 2025-11-28
tags:
  - 算法
---

# 最长公共子序列

## 题目 [最长公共子序列](https://www.acwing.com/problem/content/899/)

![[image-a80dd323.png]]

## 思路分析

![[image-f7eaca26.png]]

最长公共子序列是abd长度为3

对于这种两个序列的状态表示 可以用i表示第一个序列 j表示第二个序列

f[i][j]表示 第一个序列的前i个字母 第二个序列的前j个字母构成的子序列的最大长度

这个状态转移也可以用类似于kmp的方式进行

对比第i和第j个元素 如果相同 就说明在f[i-1][j-1]的状态下 加上这个位置的相同元素 长度+1 f[i][j]=f[i-1][j-1]+1

如果不同 就有几种情况考虑了 如果序列加上a[i]能构成新的最长公共子序列 那么状态由f[i][j-1]得来 如果序列加上b[j]能构成最长公共子序列
你们状态由f[i-1][j]得来 如果两个都不行的话 状态就仍旧为f[i-1][j-1]的样子 只需要在这几种当中 选出一个max即可

![[image-79666eb5.png]]

![[image-08e57de9.png]]

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

集合：第一个序列的前i个字母 第二个序列的前j个字母构成的子序列

属性：Max

状态计算：

if(a[i]=b[j]) f[i][j]=f[i-1][j-1]+1

else f[i][j]=max({f[i-1][j-1],f[i][j-1],f[i-1][j]});

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=1010;

char a[N],b[N];

int n,m;

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

        }

    }

    cout<<f[n][m];

    return 0;

}
```

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=1010;

char a[N],b[N];

int n,m;

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++){

            f[i][j]=max({f[i-1][j-1]+(a[i]==b[j]),f[i][j-1],f[i-1][j]});

        }

    }

    cout<<f[n][m];

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[最长公共上升子序列|最长公共上升子序列]] 🏠 [[00-刷题理模型]] ➡️ [[登山|登山]]