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;
}
?主要上述代码中特殊情况的初始化。
?