#include<iostream>
using namespace std;
int len_1 , len_2 ;
char str_1[1010] , str_2[1010];
int dp( int a , int b )
{
    if( a==-1 && b==-1 )        return 0;
    else if( a==-1 )            return b+1;
    else if( b==-1 )            return a+1;
    if( str_1[a]==str_2[b] ){
                 return   dp( a-1 , b-1 );        
    } 
    else{
                int x = dp( a-1 , b ) + 1,
                    y = dp( a , b-1 ) + 1,
                    z = dp( a-1 , b-1 ) + 1;
                return min ( min( x, y ) , z );         
    }
}
int main()
{
    while( ~scanf("%d%s%d%s" , &len_1 , str_1 , &len_2 , str_2 ) )
                 cout<<dp( len_1-1 , len_2-1 )<<endl;
    return 0;
}

• Re:dp 0ms , 230k (26) tempyy 2013-10-24 08:44:16