Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-03-15div2hard 三本勝負(SRM491, 493, 497)

SRM497 div2 第三問(1000pt) MakeSquare

|  SRM497 div2 第三問(1000pt) MakeSquare - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM497 div2 第三問(1000pt) MakeSquare - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=8681

簡単。


public class MakeSquare {
	public int diff(String a, String b) {
		int al = a.length();
		int bl = b.length();
		int dp[][] = new int[al + 1][bl + 1];
		for (int i = 0 ; i <= al ; i++) {
			dp[i][0] = i;
		}
		for (int i = 0 ; i <= bl ; i++) {
			dp[0][i] = i;
		}

		for (int i = 1 ; i <= al ; i++) {
			for (int j = 1 ; j <= bl ; j++) {
				int d = a.charAt(i-1) == b.charAt(j-1) ? 0 : 1;
				int call = Math.min(
					Math.min(dp[i-1][j] + 1, dp[i][j-1] + 1), dp[i-1][j-1] + d
				);
				if (dp[i][j] == 0) {
					dp[i][j] = call;
				} else {
					dp[i][j] = Math.min(dp[i][j], call);
				}
			}
		}
		return dp[al][bl];
	}
	public int minChanges(String S) {
		int min = S.length();
		for (int i = 1 ; i < S.length() ; i++) {
			min = Math.min(min, diff(S.substring(0, i), S.substring(i)));
		}
		return min;
	}
}