網址

http://uva.onlinejudge.org/external/111/11151.html

題目概述

給予一個字串（可為空字串），求出移除部份字元後，可得的最大迴文（Palindrome）

Technique details

第一行為測試資料數量 T (<=60)

接著 T 行字串，長度不超過 1000 ， 90% 的測試資料長度小於等於 255

輸入格式

::

2 ADAM MADAM

輸出格式

::

3 5

解題思路

字串中第 n 到 m 字移除掉部份字串後最長迴文可為下列三項的最大值

• 第 n+1 到 m 字的最長迴文
• 第 n 到 m-1 字的最長迴文
• 第 n+1 到 m-1 字的最長迴文 + 2，若第 n , m 字相同

DP 式可寫為::

dp[n][m] = max(dp[n+1][m], dp[n][m-1])
if(str[n] == str[m])
    dp[n][m] = max(dp[n][m], dp[n+1][m-1] + 2)

當 n, m 相同時，最長迴文為 1

n, m 差一時，兩字相同為 2，相異為 1