SRM497 Div2 Hard

http://www.topcoder.com/stat?c=problem_statement&pm=8681&rd=14426
問題の分析
与えられた文字列を「真ん中から前半・後半に分けたときに前半と後半が同じとなる文字列」に編集する場合の最小編集距離を求めなさい。
方針
任意の二つの文字列の最小編集距離はDPで求められる。
（GREEの伊藤直也さんの記事にDPの解説がありました。これを読めば最小編集距離の出し方はわかると思います。http://d.hatena.ne.jp/naoya/20090329/1238307757）
与えられた文字列を０〜n-1の場所で区切り、前半と後半に分ける。前半を後半と同じ文字列に編集するときの最小編集距離をすべての場所で区切った場合について求め、その最小値を返す。

ソースコード

using System;
using System.Collections.Generic;
using System.Text;
 
 
public class MakeSquare
{
    public int minChanges(String S)
    {
        int min = int.MaxValue;
        for (int i = 0; i < S.Length; i++)
        {
            string first = S.Substring(0, i);
            string second = S.Substring(i, S.Length - i);
            min = Math.Min(EditDistance(first, second), min);
        }
        return min;
    }
 
 
    private int EditDistance(string from, string to)
    {
        int[,] dp = new int[from.Length + 1, to.Length + 1];
        for (int i = 0; i < from.Length + 1; i++)
            dp[i, 0] = i;
        for (int i = 0; i < to.Length + 1; i++)
            dp[0, i] = i;
        for (int i = 1; i < from.Length + 1; i++)
        {
            for (int j = 1; j < to.Length + 1; j++)
            {
                int x;
                if (from[i - 1].Equals(to[j - 1]))
                    x = 0;
                else
                    x = 1;
                dp[i, j] = Math.Min(Math.Min(dp[i - 1, j] + 1, dp[i, j - 1] + 1), dp[i - 1, j - 1] + x);
            }
        }
        return dp[from.Length, to.Length];
    }
}