# 最長的迴文子序列

+---+---+---+---+---+---+---+
|   | 0 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+---+
| 0 | 1 |   |   |   |   |   |
+---+---+---+---+---+---+---+
| 1 |   | 1 |   |   |   |   |
+---+---+---+---+---+---+---+
| 2 |   |   | 1 |   |   |   |
+---+---+---+---+---+---+---+
| 3 |   |   |   | 1 |   |   |
+---+---+---+---+---+---+---+
| 4 |   |   |   |   | 1 |   |
+---+---+---+---+---+---+---+
| 5 |   |   |   |   |   | 1 |
+---+---+---+---+---+---+---+


j := i + Length - 1
if s[i] is equal to s[j]
dp[i][j] := 2
else
dp[i][j] := 1


+---+---+---+---+---+---+---+
|   | 0 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+---+
| 0 | 1 | 1 |   |   |   |   |
+---+---+---+---+---+---+---+
| 1 |   | 1 | 1 |   |   |   |
+---+---+---+---+---+---+---+
| 2 |   |   | 1 | 1 |   |   |
+---+---+---+---+---+---+---+
| 3 |   |   |   | 1 | 1 |   |
+---+---+---+---+---+---+---+
| 4 |   |   |   |   | 1 | 1 |
+---+---+---+---+---+---+---+
| 5 |   |   |   |   |   | 1 |
+---+---+---+---+---+---+---+


• 如果第一個和最後一個字元匹配，我們將至少有兩個專案，如果我們排除第一個和最後一個字元，我們可以從中製作 LPS +，我們可以從剩餘字串中做到最好。
• 如果第一個和最後一個字元不匹配，我們可以製作的 LPS 將來自排除我們已經計算過的第一個字元或最後一個字元。

j := i + Length - 1
if s[i] is equal to s[j]
dp[i][j] := 2 + dp[i+1][j-1]
else
dp[i][j] := max(dp[i+1][j], dp[i][j-1])
end if


+---+---+---+---+---+---+---+
|   | 0 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+---+
| 0 | 1 | 1 | 1 | 1 | 3 | 5 |
+---+---+---+---+---+---+---+
| 1 |   | 1 | 1 | 1 | 3 | 3 |
+---+---+---+---+---+---+---+
| 2 |   |   | 1 | 1 | 3 | 3 |
+---+---+---+---+---+---+---+
| 3 |   |   |   | 1 | 1 | 1 |
+---+---+---+---+---+---+---+
| 4 |   |   |   |   | 1 | 1 |
+---+---+---+---+---+---+---+
| 5 |   |   |   |   |   | 1 |
+---+---+---+---+---+---+---+


Procedure LPSLength(S):
n := S.length
dp[n][n]
for i from 0 to n
dp[i][i] := 1
end for
for i from 0 to (n-2)
if S[i] := S[i+1]
dp[i][i+1] := 2
else
dp[i][i+1] := 1
end if
end for
Length := 3
while Length <= n
for i from 0 to (n - Length)
j := i + Length - 1
if S[i] is equal to s[j]
dp[i][j] := 2 + dp[i+1][j-1]
else
dp[i][j] := max(dp[i+1][j], dp[i][j-1])
end if
end for
Length := Length + 1
end while
Return dp[0][n-1]