Codeforces 156 A. Message

問題

英小文字からなる文字列sが与えられる。sの連続する部分文字列uを任意に一つ選ぶ。
uに対して、

• 先頭または末尾に一字を加える。
• 先頭または末尾の一字を消す。
• 任意の一文字を、別の文字に変える。

の操作を行うことができる。

最小で何回の操作を行えば、tを作ることができるか、求めよ。

制約条件

sの長さ≦2000
tの長さ≦2000

方針

uの文字を消すという操作は行わなくていい。
（そんなことをするくらいなら、最初から短い文字列を選んでおけばいいから）

なので、先頭、末尾に一字加えるか、一字を別の文字に変える操作のみを考えればいい。
dp[i][j][k]を、sをi文字目まで使って、tをj文字目まで使って、
k=0のときはuがまだ始まっていなくて（先頭に文字を加えることは可能）、
k=1のときはuが始まっていて（文字を変更することのみ可能）、
k=2のときはuがおわりかけ（末尾に文字を加えることが可能）
であるようなときの、コストの最小値とする。

これを更新していくような動的計画法をすればいい。

ソースコード

int dp[2001][2001][3];

int main(){
	string a, b;
	cin>>a>>b;
	int n = a.size(), m = b.size();
	rep(i,n+1)rep(j,m+1)rep(k,3)dp[i][j][k] = inf;
	rep(i,n+1)dp[i][0][0] = 0;
	rep(i,n+1)rep(j,m+1)rep(k,3)if(dp[i][j][k] != inf){
		if(k==0&&j<m)dp[i][j+1][0] = min(dp[i][j+1][0], dp[i][j][k] + 1);
		if(j<m)dp[i][j+1][2] = min(dp[i][j+1][2], dp[i][j][k] + 1);
		if(k<2&&i<n&&j<m)dp[i+1][j+1][1] = min(dp[i+1][j+1][1], dp[i][j][k] + (a[i] != b[j]));
	}
	int ans = inf;
	rep(i,n+1)rep(k,3)ans = min(ans, dp[i][m][k]);
	cout<<ans<<endl;
	return 0;
}