AcWing 902. 最短編輯距離
這道題是用線性dp就可以解決，在這之前，我先給大家介紹一下我們大名鼎鼎的閆氏dp
首先我們要考慮狀態表示，dp[i,j]表示a[1
?
-
?i]變成b[1
?
-
?j]的最小操作方案數，我們可以假設成dp[i,j]是成功把a[1~~i]變成b[1~j]的
然后狀態計算，洗掉操作是在i-1,j已經匹配上了，多了一個i,那么我們就把它刪了，插入操作是指，i,j-1匹配上了，但是我們要匹配上i,j需要再加一個字母，如果a[i]==b[j]那么我們就不需要改了，就直接使用dp[i-1][j-1]要是不匹配上就使用dp[i-1][j-1]
不管怎么說，代碼如下
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
char a[N],b[N];
int dp[N][N];
int main(void)
{
int n,m;
cin>>n;
scanf("%s",a+1);
cin>>m;
scanf("%s",b+1);
//這一步很重要
for(int i=1;i<=n;i++) dp[i][0]=i;//一直刪
for(int i=1;i<=m;i++) dp[0][i]=i;//一直插
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1);
if(a[i]==b[j])
dp[i][j]=min(dp[i][j],dp[i-1][j-1]);
else
dp[i][j]=min(dp[i][j],dp[i-1][j-1]+1);
}
cout<<dp[n][m];
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/262471.html
標籤：其他