摘要：
对于任意两个字符串A和B，计算用于将字符串A转换为字符串B的最小字符操作数。给定两个字符串S和T，至少可以修改S中的多少字符以使S包含T？
这一题类似于距离编辑，所以我们首先来看看什么是编辑距离。
题目 2141: [信息学奥赛一本通-T1276 ]编辑距离 https://www.dotcpp.com/oj/problem2141.html
题目描述
设A和B是两个字符串。我们要用最少的字符操作次数，将字符串A转换为字符串B。这里所说的字符操作共有三种：
1、删除一个字符；
2、插入一个字符；
3、将一个字符改为另一个字符。
对任意的两个字符串A和B，计算出将字符串A变换为字符串B所用的最少字符操作次数。
解决思路：
1、删除一个字符；
2、插入一个字符；
3、将一个字符改为另一个字符。
对任意的两个字符串A和B，计算出将字符串A变换为字符串B所用的最少字符操作次数。
解决思路：
dp求解。设dp[ i ][ j ]为将字符串A[ 1,...,i ] 转变为字符串 B[ 1,...,j ]所用的最小字符操作次数。
边界情况:
dp[ 0 ][ 0 ] = 0 (两个空串)
dp[ i ][ 0 ] = i (对A[ 1,...,i ] 重复进行 i 次删除操作)
dp[ 0 ][ j ] = j (对空串A重复进行 j 次插入操作)
递推式:
dp[ i ][ j ] = dp[ i ][ j-1 ] + 1 ( 在A[ 1,...,i ]的尾部插入B[ j ] )
dp[ i ][ j ] = dp[ i-1 ][ j ] + 1 ( 删去A[ 1,...,i ]的尾部A[ i ] )
dp[ i ][ j ] = dp[ i-1 ][ j-1 ] + (A[ i ]==B[ j ] ? 0 : 1 ) (如果不相等则将A[ i ]替换为B[ j ]，否则不需要替换 )
dp[ i ][ j ] 在上述三种可能中取最小(对应于三种操作)
实现代码:
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int Max_N = 2e3+10; char A[Max_N],B[Max_N]; int dp[Max_N][Max_N]; int main() { scanf("%s%s",A+1,B+1);//下标从1开始 便于操作 int len_A = strlen(A+1), len_B = strlen(B+1); //边界情况 dp[0][0] = 0; for( int i=1; i<=len_A; i++ ) dp[i][0] = i; for( int j=1; j<=len_B; j++ ) dp[0][j] = j; //递推式 for( int i=1; i<=len_A; i++ ) { for( int j=1; j<=len_B; j++ ) { int temp = min( dp[i][j-1], dp[i-1][j] ) + 1; int d = A[i]==B[j] ? 0 : 1; dp[i][j] = min( temp, dp[i-1][j-1]+d ); } } printf("%d ",dp[len_A][len_B]); return 0; }
最优包含 https://www.acwing.com/problem/content/2555/
2553. 最优包含
我们称一个字符串 S 包含字符串 T 是指 T 是 S 的一个子序列，即可以从字符串 S 中抽出若干个字符，它们按原来的顺序组合成一个新的字符串与 T 完全一样。
给定两个字符串 S 和 T，请问最少修改 S 中的多少个字符，能使 S 包含 T？
解题思路:
与编辑距离不同的是题目只要求包含且只有替换操作。仍然用dp方法。
设dp[ i ][ j ] : S[ 1,...,i ]需要修改多少个字符能包含T[ 1,...,j ]
边界情况:
dp[ i ][ 0 ] = 0 (不需要替换)
dp[ i ][ j ] = INF i<=j or len_S-i <= len_T-j (我当时遇到的问题就是如何保证S中有足够的字符能替换为T，只需要保证i>=j即之前
有足够字符且len_S-i <= len_T-j 即之后有足够字符，实现时只需要将边界dp[ 0 ][ j ] = INF )
递推式:
dp[ i ][ j ] = dp[ i-1 ][ j ] (S[ 1,...,i-1 ]已经包含了T[ 1,...,j ] )
dp[ i ][ j ] = dp[ i-1 ][ j-1 ] + (S[ i ]==T[ j ] ? 0 : 1 )
实现代码:
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int INF = 1e8+10; const int Max_N = 1e3+10; char S[Max_N],T[Max_N]; int dp[Max_N][Max_N]; int main() { scanf("%s%s",S+1,T+1); int len_S = strlen(S+1), len_T = strlen(T+1); //初始化 dp[0][0] = 0; for( int i=1; i<=len_S; i++ ) dp[i][0] = 0; for( int j=1; j<=len_T; j++ ) dp[0][j] = INF; //递推 for( int i=1; i<=len_S; i++ ) { for( int j=1; j<=len_T; j++ ) { int d = S[i]==T[j] ? 0 : 1; dp[i][j] = min( dp[i-1][j], dp[i-1][j-1]+d ); } } printf("%d ",dp[len_S][len_T]); return 0; }
参考连接 https://www.cnblogs.com/biyeymyhjob/archive/2012/09/28/2707343.html