1159:Palindrome

問題文
http://poj.org/problem?id=1159

与えられた文字列を、文字を挿入する操作のみを行って回文にする。挿入する文字の最小個数を求めよ。

↓と同じ。メモ化再帰。int型を使うとMLEする。
http://d.hatena.ne.jp/TobiasGSmollett/20130702/1372785990

#include<iostream>
#include<algorithm>
#include<string>
#define INF (1<<13)

using namespace std;

short memo[5001][5001];
string s;

short rec(int i,int j){

  if(memo[i][j]<INF)return memo[i][j];
  if(i>=j)return 0;

  short res=INF;
  if(s[i]==s[j])res=min(res,rec(i+1,j-1));
  else res=min(rec(i+1,j),rec(i,j-1))+1;

  return memo[i][j]=res;
}

int main(void){

  int n;
  cin >> n >> s;
  fill(memo[0],memo[5001],INF);
  cout << rec(0,s.size()-1) << endl;

  return 0;
}