dp中最短编辑距离的笔记（分析dp）

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;
}

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

?