http://172.20.16.106/JudgeOnline/showproblem?problem_id=1035http://acm.nankai.edu.cn/p1131.htmlDP代码
#include<iostream>
#include<string>
using namespace std;
const int N = 2001;//用1001 Runtime Error,不要开得太小
int dp[N][N];//dp[i][j]表示串s的前i个字符匹配到串t的前j个字符的最小步数
int lens,lent;
char s[N],t[N];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int i,j;
while(scanf("%s%s",s,t)!=EOF)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
lens = strlen(s);
lent = strlen(t);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=0;i<=lens;i++)
dp[i][0] = i;
for(j=0;j<=lent;j++)
dp[0][j] = j;//变换到第j个字符最多用j步
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=1;i<=lens;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
for(j=1;j<=lent;j++)//目标串指针
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if(s[i-1] == t[j-1])
dp[i][j] = dp[i-1][j-1];
else //更改
dp[i][j] = dp[i-1][j-1] + 1;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(dp[i][j] > dp[i-1][j] + 1)//删除第i个
dp[i][j] = dp[i-1][j] + 1;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(dp[i][j] > dp[i][j-1] + 1)//插入第i个
dp[i][j] = dp[i][j-1] + 1;
}
}
printf("%d\n",dp[lens][lent]);
}
return 0;
}
DFS代码(在南开JudgeOnline超时)
#include<iostream>
#include<string>
using namespace std;
const int M = 10000000;
const int N = 2001;//用1001 Runtime Error,不要开得太小
int dp[N][N];
int lens,lent;
char s[N],t[N];
int dfs(int i,int j)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int p,q,r,mins=M;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(i == lens && j == lent )
return 0;
else if(i == lens && j != lent )
return lent - j;
else if(i != lens && j == lent )
return lens - i;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(dp[i][j] != M) //做过的没有必要再做
return dp[i][j];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(s[i] == t[j])
mins = dfs(i+1,j+1);//不用改变
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
p = dfs(i+1,j+1) + 1;//修改
q = dfs(i+1,j) + 1;//删除
r = dfs(i,j+1) + 1;//插入
if(p > q)
mins = q;
else
mins = p;
if(mins > r)
mins = r;
}
dp[i][j] = mins;
return mins;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int i,j;
while(scanf("%s%s",s,t)!=EOF)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
lens = strlen(s);
lent = strlen(t);
for(i=0;i<lens;i++)
for(j=0;j<lent;j++)
dp[i][j] = M;
dfs(0,0);
printf("%d\n",dp[0][0]);
}
return 0;
}
|