【动态规划】最长公共子序列

博主： Fivk
发布时间：2022 年 01 月 07 日
1218 次浏览
暂无评论
1265字数
分类：题目典例

给定两个长度分别为 N 和 M 的字符串 A 和 B，求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。

#### 输入格式

第一行包含两个整数 N 和 M。

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

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

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

#### 输出格式

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

#### 数据范围

1≤N,M≤1000

#### 输入样例：

```
4 5
acbd
abedc
```

#### 输出样例：

```
3
```

#### 基本思考框架

![](https://blog.fivk.cn/usr/uploads/2022/01/3377658528.png)

集合表示：`f[i][j]`表示`a`的前`i`个字母，和`b`的前`j`个字母的最长公共子序列长度

集合划分：以`a[i]`, `b[j]`是否包含在子序列当中为依据，因此可以分成四类：

---

①`a[i]`不在，`b[j]`不在

$max=f[i−1][j−1]$

---

②`a[i]`不在，`b[j]`在

看似是$max=f[i−1][j]$ , 实际上无法用$f[i−1][j]$表示，因为$f[i−1][j]$表示的是在`a`的前`i-1`个字母中出现，并且在`b`的前`j`个字母中出现,此时`b[j]`不一定出现，这与条件不完全相等，条件给定是`a[i]`一定不在子序列中，`b[j]`一定在子序列当中，但仍可以用`f[i−1][j]`来表示，原因就在于条件给定的情况被包含在`f[i−1][j]`中，即条件的情况是`f[i−1][j]`的子集，而求的是`max`，所以对结果不影响。

> 例如：要求`a，b，c`的最大值可以这样求：$max(max(a,b),max(b,c))$虽然`b`被重复使用，但仍能求出`max`，求`max`只要保证不漏即可。

---

③`a[i]`在，`b[j]`不在 原理同②

---

④`a[i]`在，`b[j]`在 $max=f[i−1][j−1]+1;$

> 实际上，在计算时，①包含在②和③的情况中，所以①不用考虑

#### C++代码

```cpp
#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;
    cin >> 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] , f[i][j - 1]);//②和③的情况一定存在，所以可以无条件优先判断
                if(a[i] == b[j]) f[i][j] = max(f[i][j] , f[i - 1][j - 1] + 1);
            }

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

#### 思路2

##### 问题分析

这题的状态分成两半考虑，按两个序列末尾的字符是不是相等来区分。

![问题分析.PNG](https://blog.fivk.cn/usr/uploads/2022/01/677264189.png)

如果两个字符相等，就可以直接转移到`f[i-1][j-1]`，不相等的话，两个字符一定有一个可以抛弃，可以对`f[i-1][j]`,`f[i][j-1]`两种状态取`max`来转移。

![状态转移.PNG](https://blog.fivk.cn/usr/uploads/2022/01/2908969055.png)

#### C++代码

代码实现差不多

```cpp
#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;
  return 0;
}
```

最后修改：2022 年 01 月 07 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

【动态规划】最长公共子序列

Fivk • 2022 年 01 月 07 日

给定两个长度分别为 N 和 M 的字符串 A 和 B，求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。

#### 输入格式

第一行包含两个整数 N 和 M。

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

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

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

#### 输出格式

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

#### 数据范围

1≤N,M≤1000

#### 输入样例：

```
4 5
acbd
abedc
```

#### 输出样例：

```
3
```

#### 基本思考框架

![](https://blog.fivk.cn/usr/uploads/2022/01/3377658528.png)

集合表示：`f[i][j]`表示`a`的前`i`个字母，和`b`的前`j`个字母的最长公共子序列长度

集合划分：以`a[i]`, `b[j]`是否包含在子序列当中为依据，因此可以分成四类：

---

①`a[i]`不在，`b[j]`不在

$max=f[i−1][j−1]$

---

②`a[i]`不在，`b[j]`在

> 例如：要求`a，b，c`的最大值可以这样求：$max(max(a,b),max(b,c))$虽然`b`被重复使用，但仍能求出`max`，求`max`只要保证不漏即可。

---

③`a[i]`在，`b[j]`不在 原理同②

---

④`a[i]`在，`b[j]`在 $max=f[i−1][j−1]+1;$

> 实际上，在计算时，①包含在②和③的情况中，所以①不用考虑

#### C++代码

```cpp
#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;
    cin >> a + 1 >> b + 1;

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

#### 思路2

##### 问题分析

这题的状态分成两半考虑，按两个序列末尾的字符是不是相等来区分。

![问题分析.PNG](https://blog.fivk.cn/usr/uploads/2022/01/677264189.png)

如果两个字符相等，就可以直接转移到`f[i-1][j-1]`，不相等的话，两个字符一定有一个可以抛弃，可以对`f[i-1][j]`,`f[i][j-1]`两种状态取`max`来转移。

![状态转移.PNG](https://blog.fivk.cn/usr/uploads/2022/01/2908969055.png)

#### C++代码

代码实现差不多

```cpp
#include <iostream>
using namespace std;

const int N = 1010;

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

【动态规划】最长公共子序列

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

【踩坑日志】SpringBoot项目启动提示This primary key of "id" is primitive !不建议如此请使用包装类 in Class:

【C】极域电子教室学生端解除控制

【开发技巧】@CrossOrigin注解解决跨域问题

【Fivk】文章归档

回忆刚入天柱二中的我

【C】文件_文件的随机读写(rewind ，ftell，fseek)

【Java】关键字、标识符、注释

【Java】常用类之Object、Objects

【Fivk】文章归档

【期末复习】java程序设计习题答案

【动态规划】最长公共子序列

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

【动态规划】最长公共子序列

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款