http://172.20.16.106/JudgeOnline/showproblem?problem_id=1035
http://acm.nankai.edu.cn/p1131.html
DP代码
#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];

int main()
{
    
int i,j;
    
while(scanf("%s%s",s,t)!=EOF)
    
{
        lens 
= strlen(s);
        lent 
= strlen(t);

        
for(i=0;i<=lens;i++)
            dp[i][
0= i;
        
for(j=0;j<=lent;j++)
            dp[
0][j] = j;//变换到第j个字符最多用j步

        
for(i=1;i<=lens;i++)        
        
{   
            
for(j=1;j<=lent;j++)//目标串指针
            {
                
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;

                
if(dp[i][j] > dp[i-1][j] + 1)//删除第i个
                    dp[i][j] = dp[i-1][j] + 1;

                
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)
{
    
int p,q,r,mins=M;

    
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;

    
if(dp[i][j] != M) //做过的没有必要再做
        return dp[i][j];

    
if(s[i] == t[j])
        mins 
= dfs(i+1,j+1);//不用改变
    else
    
{
        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;
}


int main()
{
    
int i,j;
    
while(scanf("%s%s",s,t)!=EOF)
    
{
        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;
}