POJ 1159 Palindrome

DP強化週間。
与えられた文字列にあらたな文字を挿入して回文にするときに必要となる
最小の文字数。dp[i][j] := (str[i...j]を回文とするのに必要な最小文字数)でDP。
intだとMLE。

short dp[5001][5001];

int main(){
  int N;
  string s;
  cin >> N;
  cin >> s;

  for(int i = N - 1; i >= 0; i--){
    for(int j = i; j < N; j++){
      if(s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1];
      else dp[i][j] = 1 + min(dp[i + 1][j], dp[i][j - 1]);
    }
  }
  cout << dp[0][N - 1] << endl;
  return 0;
}

ぶっちゃけこんな簡単なのに全部自力で解けたのではないので、ちゃんと復習したい。