dp中最短编辑距离的笔记(分析dp)

发布时间:2023年12月18日

dp分析往往就是看最后一步的变化。

分析:

?设a串长度为i,b串长度为j。题目要求为通过三种操作将a字符串转化为b字符串的最少次数。

删除操作:

? ? ? ? ? ? ? ? 把a[i]删除后a[1~i]和b[1~j]匹配,所以可以得到f[i - 1][j] + 1,在此之前要先做到a[1~i-1]和b[1~j]匹配。

增加操作:

? ? ? ? ? ? ? ? 将a[i + 1]添加后a[1~i]和b[1~j]匹配,所以可以得到f[i][j - 1] + 1,在此之前先要得到a[1~i]和b[1~j - 1]匹配。

替换操作:

? ? ? ? ? ? ? ?如果a[i]和a[j]的值相等,那么得到f[i - 1][j - 1]。如果不相等那么得到f[i - 1][j - 1] + 1。无论a[i]和a[j]的值是否相等,a[1~i -1]和b[1~j - 1]都是匹配的。

?

代码如下:

//最短距离编辑
//dp的分类一般都是考虑最后一步的选法
#include<iostream>
using namespace std;
const int N = 1e3 + 9;
int n, m, f[N][N];
char a[N], b[N];

int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> a + 1;
	cin >> m >> b + 1;
	//特殊情况:a有0个字符串,需要增加b长度的字符串次操作
	for (int i = 0; i <= m; ++i) f[0][i] = i;
	//特殊情况:b有0个字符串,需要删除a长度的字符串次操作
	for (int i = 0; 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);
			if (a[i] == b[j]) f[i][j] = min(f[i - 1][j - 1], f[i][j]);
			else f[i][j] = min(f[i - 1][j - 1] + 1, f[i][j]);
		}
	}
	cout << f[n][m];
	return 0;
}

?主要上述代码中特殊情况的初始化。

?

文章来源:https://blog.csdn.net/qq_73185160/article/details/135045598
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。