版本 1fd52682835afc077b4b69d5294f64ad5b8d7c06

11151

Changes from beginning to 1fd52682835afc077b4b69d5294f64ad5b8d7c06

---
title: [UVa] 11151 - Longest Palindrome
toc: no
categories: 題解 UVa DP string_processing_字串處理
...

網址
====

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