牛客训练（处女座与复读机）dp解法

曾经终败给现在 2022-04-23 07:12 206阅读 0赞

大佬的思想：[https://blog.csdn.net/snayf/article/details/86632559][https_blog.csdn.net_snayf_article_details_86632559]

题目描述  
一天，处女座在牛客算法群里发了一句“我好强啊”，引起无数的复读，可是处女座发现复读之后变成了“处女座好强啊”。处女座经过调查发现群里的复读机都是失真的复读机，会固定的产生两个错误。一个错误可以是下面的形式之一：

1.       将任意一个小写字母替换成另外一个小写字母

2.       在任意位置添加一个小写字母

3.       删除任意一个字母

处女座现在在群里发了一句话，他收到了一个回应，他想知道这是不是一个复读机。

输入描述:  
两行  
第一行是处女座说的话s  
第二行是收到的回应t  
s和t只由小写字母构成且长度小于100  
输出描述:  
如果这可能是一个复读机输出”YES”，否则输出”NO”  
示例1

输入  
abc  
abcde  
输出  
YES  
说明  
abc->abcd->abcde  
示例2

输入  
abcde  
abcde  
输出  
YES  
说明  
abcde->abcdd->abcde  
备注:  
只要能经过两步变换就从s得到t就有可能是复读机。

dp解法：  
 d\[i\]\[j\]表示a串前i个字符变换为b串前j个字符所需要的最小步骤  
 dp\[i\]\[j\]=min(dp\[i-1\]\[j\],dp\[i\]\[j-1\])+1;注：当字符串不同时，和动态规划公共子串一样的方法,dp\[i\]\[j\]是变换a\[i\]和变换b\[j\]两种选择中最小的一部分   
 dp\[i\]\[j\]=min(dp\[i\]\[j\],dp\[i-1\]\[j-1\]+(a\[i\]!=b\[j\])) 注：当字符相同时， 不进行操作

#include<bits/stdc++.h>//LCS
    #include<string>
    using namespace std;
    /*dp解法：
     d[i][j]表示a串前i个字符变换为b串前j个字符所需要的最小步骤
     dp[i][j]=min(dp[i-1][j],dp[i][j-1])+1;注：当字符串不同时，和动态规划公共子串一样的方法,dp[i][j]是变换a[i]和变换b[j]两种选择中最小的一部分 
     dp[i][j]=min(dp[i][j],dp[i-1][j-1]+(a[i]!=b[j])) 注：当字符相同时， 不进行操作 
    */
    int dp[105][105];
    int main(){
    	string a,b;
    	cin>>a>>b;
    	int n=a.length(),m=b.length(),t; 
    	for(int i=1;i<=n;i++)
    		for(int j=1;j<=m;j++){
    			dp[i][j]=min(dp[i-1][j],dp[i][j-1])+1;
    			dp[i][j]=min(dp[i][j],dp[i-1][j-1]+(a[i-1]!=b[j-1]));
    		}
    	if(dp[n][m]>2)cout<<"NO";
    	else cout<<"YES";
    	return 0;
    }

[https_blog.csdn.net_snayf_article_details_86632559]: https://blog.csdn.net/snayf/article/details/86632559