网站流量超标,小程序开发公司主页制作标准,建设个网站,著名的响应式网站有哪些题目描述2988:计算字符串距离
对于两个不同的字符串#xff0c;我们有一套操作方法来把他们变得相同#xff0c;具体方法为#xff1a;
修改一个字符#xff08;如把“a”替换为“b”#xff09;删除一个字符#xff08;如把“traveling”变为“travelng”#xff09;…题目描述2988:计算字符串距离
对于两个不同的字符串我们有一套操作方法来把他们变得相同具体方法为
修改一个字符如把“a”替换为“b”删除一个字符如把“traveling”变为“travelng” 比如对于“abcdefg”和“abcdef”两个字符串来说我们认为可以通过增加/减少一个“g”的方式来达到目的。无论增加还是减少“g”我们都仅仅需要一次操作。我们把这个操作所需要的次数定义为两个字符串的距离。 给定任意两个字符串写出一个算法来计算出他们的距离。 输入 第一行有一个整数n。表示测试数据的组数 接下来共n行每行两个字符串用空格隔开。表示要计算距离的两个字符串 字符串长度不超过1000。 输出 针对每一组测试数据输出一个整数值为两个字符串的距离。
解析
使用dp转移
if(a[i]b[j]) dp[i][j]dp[i-1][j-1];
else{dp[i][j]min(dp[i-1][j-1]修改,min(dp[i-1][j]删前,dp[i][j-1]删后))1;
}就完事啦
问题
然而… 又出了一堆bug 勿忘国耻
1.定义
一开始又草率了qwq 这题不能用最长公共子序列 其实很显然 但想dp的时候就是看不到 第n次了 dp一定要谨慎
2.初始化
少了一行很关键的东西
for(int i1;imax(l1,l2);i) dp[i][0]dp[0][i]i;实际意义也很显然 所以dp的初始化也是要重视的 很多时候不止是赋个dp[0][0]0这么简单
代码
#includebits/stdc.h
using namespace std;
#define ll long long
const int N2e3100;
int n,m;
char a[N],b[N];
int dp[N][N],l1,l2;
int main(){scanf(%d,n);for(int k1;kn;k){scanf( %s,a1);scanf( %s,b1);l1strlen(a1);l2strlen(b1);//couta1;dp[0][0]0;for(int i1;imax(l1,l2);i) dp[i][0]dp[0][i]i;
// int mmax(l1,l2);for(int i1;il1;i){for(int j1;jl2;j){if(a[i]b[j]) dp[i][j]dp[i-1][j-1];else{dp[i][j]min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))1;}
// printf(i%d j%d dp%d\n,i,j,dp[i][j]);}}printf(%d\n,dp[l1][l2]);}return 0;
}
/*
3
abcdefg abcdef
ab ab
mnklj jlknm
*/
