题目链接：传送门
编辑距离问题Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KBTotal submit users: 21, Accepted users: 18Problem 10271 : No special judgementProblem description 设A 和B 是2 个字符串。要用最少的字符操作将字符串A 转换为字符串B。这里所说的 字符操作包括 (1)删除一个字符； (2)插入一个字符； (3)将一个字符改为另一个字符。 将字符串A变换为字符串B 所用的最少字符操作数称为字符串A到B 的编辑距离，记为 d(A,B)。试设计一个有效算法，对任给的2 个字符串A和B，计算出它们的编辑距离d(A,B)。 Input 输入的第一行是字符串A，文件的第二行是字符串B。 Output 程序运行结束时，将编辑距离d(A,B)输出。 Sample Input fxpimu xwrs Sample Output 5
解题思路：动态规划
d[i][j],i为A字符串的当前长度，j为B字符串的当前长度
i=0,d[i][j]=j
j=0,d[i][j]=i
i>0,j>0,d[i][j]=min(d[i-1][j]+1,d[i][j-1]+1,d[i-1][j-1]+d) A[i]=B[j]时d=0，否则d=1
吐槽一下：A,B字符串长度也不给出来，为啥开的10000*10000的数组都没爆内存
#include <cstdio> #include <cstring> #include <cmath> #include <iostream> #include <queue> #include <set> #include <string> #include <stack> #include <algorithm> #include <map> using namespace std; typedef long long ll; const int N = 10007; const int M = 100000000; const int INF = 0x3fffffff; const int mod = 1e9+7; const double Pi = acos(-1.0); const double sm = 1e-9; int dp[N][N]; int main() { string A,B; while( cin >> A >> B ){ dp[0][0] = 0; for( int i = 1 ; i <= A.length() ; ++i ) dp[0][i] = i; for( int j = 1 ; j <= B.length() ; ++j ) dp[j][0] = j; for( int i = 0 ; i < B.length() ; ++i ){ for( int j = 0 ; j < A.length() ; ++j ){ dp[i+1][j+1] = min( dp[i][j+1]+1 , dp[i+1][j]+1 ); if( A[j] == B[i] ) dp[i+1][j+1] = min( dp[i+1][j+1] , dp[i][j] ); else dp[i+1][j+1] = min( dp[i+1][j+1] , dp[i][j]+1 ); } } printf("%d\n",dp[B.length()][A.length()]); } return 0; }
