题目
思路
状态表示
集合:将$a[1-i]$变成$b[1-j]$的操作方式
属性:min(次数最小)
状态计算 :从最后一步考虑
有三种操作,所以有三个子集
ok子集划分完了
考虑状态转移的时候
先考虑如果我没有进行这个操作应该是什么状态
然后考虑你进行这一步操作之后会对你下一个状态造成什么影响
然后再加上之前状态表示中你决策出来的那个DP属性
这样就可以自然而然地搞出来转移方程啦
-
1)删除操作:把$a[i]$删掉之后$a[1-i]$和$b[1-j]$匹配
所以之前要先做到$a[1-(i-1)]$和$b[1-j]$匹配
$f[i-1][j] + 1$ -
2)插入操作:插入之后$a[i]$与$b[j]$完全匹配,所以插入的就是$b[j]$
那填之前$a[1-i]$和$b[1-(j-1)]$匹配
$f[i][j-1] + 1$ -
3)替换操作:把$a[i]$改成$b[j]$之后想要$a[1-i]$与$b[1-j]$匹配
那么修改这一位之前,$a[1-(i-1)]$应该与$b[1-(j-1)]$匹配
$f[i-1][j-1] + 1$
但是如果本来a[i]与b[j]这一位上就相等,那么不用改,即
$f[i-1][j-1] + 0$
好的那么$f[i][j]$就由以上三个可能状态转移过来,取个$min$
dp初始化
细节问题:初始化怎么搞
先考虑有哪些初始化嘛
+ 1.你看看在for遍历的时候需要用到的但是你事先没有的
(往往就是什么0啊1啊之类的)就要预处理
+ 2.如果要找$min$的话别忘了INF
要找有负数的$max$的话别忘了-INF
ok对应的:
+ 1.$f[0][i]$如果a初始长度就是0,那么只能用插入操作让它变成b
$f[i][0]$同样地,如果b的长度是0,那么a只能用删除操作让它变成b
代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int n,m;
char a[N],b[N];
int f[N][N];
int main()
{
scanf("%d%s",&n,a+1);
scanf("%d%s",&m,b+1);
for(int i=0;i<=n;i++) f[i][0]=i; //如果b串为空,那么a串只能通过删除操作,b有多长,删多少
for(int i=0;i<=m;i++) f[0][i]=i; //如果a串为空,那么a串只能通过插入操作,b串有多长,插多少
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][j],f[i-1][j-1]); //再去算更改操作的最小值 这一行对应不用改(本来就相等)
else f[i][j]=min(f[i][j],f[i-1][j-1]+1); //需要改,本来不等
}
printf("%d",f[n][m]);
return 0;
}
问题