SRM497 Div2 Hard(1000) MakeSquare - kusano

min{編集距離(S[0..i],S[i+1..n-1])}

#include <string>
#include <vector>
using namespace std;

//  編集距離
int editdistance( string a, string b )
{
    int n=(int)a.length();
    int m=(int)b.length();
    vector<vector<int> >T(n+1,vector<int>(m+1));
    for(int i=0;i<=n;i++)T[i][0]=i;
    for(int j=0;j<=m;j++)T[0][j]=j;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
        T[i][j]=min(T[i][j-1],min(T[i-1][j],T[i-1][j-1]-(a[i-1]==b[j-1])))+1;
    return T[n][m];
}

class MakeSquare{public:
int minChanges( string S )
{
    int n = (int)S.length();
    int ans = n;
    for ( int i=0; i<=n; i++ )
        ans = min( ans, editdistance(S.substr(0,i),S.substr(i,n-i)) );
    return ans;
}};