时间复杂度 O(n^2)
C++ 代码
#include<iostream>
using namespace std ;
const int N = 1010 ;
char a[N] ,b[N] ;
int dp[N][N] ; // dp[i][j] ; 表示将前i个a串变为前j个字母的B串的最少需要操作的次数
int main() // 划分是安照删的逻辑:dp[i-1][j] 即a前i个字母和b的前j-1个字母一致 ;和添加的逻辑dp[i][j-1]:
{
int n ;
cin>>n ;
for(int i =1 ;i<= n ; ++i)
{
cin>>a[i];
}
int m ;
cin>>m;
for(int i =1 ; i<= m ;++i)
{
cin>>b[i] ;
}
// 将A变为B 需要最少多少次操作,
for(int i = 1 ; i <= n ; ++i)
{
dp[i][0] = i; // a要与b的第0个串一样需要进行i次删减操作
}
for(int i = 1 ; i<= m ; ++i)
{
dp[0][i] = i ; // a从第0个字母,变为与b的前i个字母一样需要i次增加操作
}
for(int i = 1 ; i <= n ; ++i)
for(int j = 1; j<= m ; ++j)
{
dp[i][j] = min(dp[i][j-1] +1 , dp[i-1][j] +1 ); // 对于当前i, j的集合的情况 。 所代表的划分集合dp[i][j-1]和 dp[i-1][j]一定存在 ; 所以先计算这两个集合的最大值。
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]<<endl;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla