10739:String to Palindrome

問題文
http://uva.onlinejudge.org/external/107/10739.html

文字列が与えられる。ある１文字を追加、削除、置換することができる。
この３つの操作を繰り返すことで回文を作りたい。
操作を繰り返す回数の最小回数を求めよ。

      l       r      l     r
追加  e b c d a    e b c d a e   eを追加してl+1

      l         r   l       r
削除  a b c d a e   a b c d a    eを削除してr-1

      l       r      l   r  
置換  a b c d e    a b c d a     eをaに置換してl+1, r-1

というのを再帰関数で書いて、メモ化した。

#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

int memo[1001][1001];
string s;

int rec(int l,int r){
  if(l>=r)return 0;
  if(memo[l][r]>0)return memo[l][r];
  int res=min(rec(l+1,r),rec(l,r-1))+1;
  res=min(res,rec(l+1,r-1)+(s[l]!=s[r]));
  return memo[l][r]=res;
}

int main(void){

  int n;
  cin >> n;
  for(int i=1;i<=n;i++){
    fill(memo[0],memo[1001],0);
    cin >> s;
    cout << "Case " << i << ": " << rec(0,s.size()-1) <<endl;
  }
  return 0;
}