UVa 10739 : String to Palindrome

UVa演習 2014/6/24 (火) 問１

問題リンク : http://uva.onlinejudge.org/external/107/10739.html

問題概要：
長さ１０００以下の文字列が与えられる
この文字列のアルファベットに対して以下の３つの操作を自由に使うことができる
・任意の場所に任意のアルファベットを追加する
・任意の場所のアルファベットを削除する
・任意の場所のアルファベットを任意のアルファベットに置換する
与えられた文字列を回文にするために必要な最小の操作の回数を求めよ

解法：
メモ化再帰
UVa 11753の類題

コード:

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

const int IINF = INT_MAX;
char s[1010];
int memo[1010][1010];

int dfs(int L,int R){

  if( memo[L][R] != IINF ) return memo[L][R];
  if( L >= R ) return 0;
  if( s[L] == s[R] ) return memo[L][R] = dfs(L+1,R-1);
  int ret = min(dfs(L+1,R)+1,dfs(L,R-1)+1);// add and remove
  ret = min(ret,dfs(L+1,R-1)+1); // Replace
  return memo[L][R] = ret;
}

int main(){
  int T,CNT=1;
  scanf("%d",&T);
  while( T-- ){
    scanf(" %s",&s[0]);
    printf("Case %d: ",CNT++);
    int LEN = strlen(s);
    rep(i,LEN+1) rep(j,LEN+1) memo[i][j] = IINF;
    printf("%d\n",dfs(0,LEN-1));
  }
  return 0;
}