問題描述：516. 最長回文子序列
給定一個字元串 s ，找到其中最長的回文子序列，并傳回該序列的長度。可以假設 s 的最大長度為 1000 。
示例 1:
輸入:
"bbbab"
輸出:
4
一個可能的最長回文子序列為 "bbbb"。
示例 2:
輸入:
"cbbd"
輸出:
2
一個可能的最長回文子序列為 "bb"。
方法一：斜線周遊
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
n = len(s)
dp = [[0]*(n) for i in range(n)]
for i in range(n):
dp[i][i] = 1
#l 為偏移量
for l in range(1,n):
for i in range(n-l):
j = i + l
if s[i] == s[j]:
dp[i][j] = dp[i+1][j-1]+2
else:
dp[i][j] = max(dp[i+1][j],dp[i][j-1])
return dp[0][n-1]
方法二：斜向下周遊+狀态壓縮
import copy
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
n = len(s)
dp = [1 for i in range(n)]
pre = [0 for i in range(n)]
tmp = [0 for i in range(n)]
for l in range(1,n):
for i in range(n-l):
j = i + l
//每次重新開啟外循環時，l-1的元素要重新指派,獲得每次外循環開始的dp[i][j-1]元素
//參考(0,1)(0,2)(0.3)(0,4)步驟 外循環新觸發時元素的更新
tmp[l-1] = dp[l-1]
//獲得dp[i+1][j]
tmp[j] = dp[j]
if s[i] == s[j]:
dp[j] = pre[j-1] + 2 //pre[j-1]就是dp[i+1][j-1]
else:
dp[j] = max(tmp[j-1], tmp[j])
//不能放在for内循環，因為每次都會更新pre數組，導緻dp[i+1][j-1]被更新，參考(1,4)步驟
pre = copy.deepcopy(tmp)
return dp[n-1]
以測試集'bbbab'為例
| l | (i,j) | tmp | dp | pre |
| 1 | (0, 1) | [1, 1, 0, 0, 0] | [1, 2, 1, 1, 1] | [0, 0, 0, 0, 0] |
| 1 | (1, 2) | [1, 1, 1, 0, 0] | [1, 2, 2, 1, 1] | [0, 0, 0, 0, 0] |
| 1 | (2, 3) | [1, 1, 1, 1, 0] | [1, 2, 2, 1, 1] | [0, 0, 0, 0, 0] |
| 1 | (3, 4) | [1, 1, 1, 1, 1] | [1, 2, 2, 1, 1] | [0, 0, 0, 0, 0] |
| 2 | (0, 2) | [1, 2, 2, 1, 1] | [1, 2, 3, 1, 1] | [1, 1, 1, 1, 1] |
| 2 | (1, 3) | [1, 2, 2, 1, 1] | [1, 2, 3, 2, 1] | [1, 1, 1, 1, 1] |
| 2 | (2, 4) | [1, 2, 2, 1, 1] | [1, 2, 3, 2, 3] | [1, 1, 1, 1, 1] |
| 3 | (0, 3) | [1, 2, 3, 2, 1] | [1, 2, 3, 3, 3] | [1, 2, 2, 1, 1] |
| 3 | (1, 4) | [1, 2, 3, 2, 3] | [1, 2, 3, 3, 3] | [1, 2, 2, 1, 1] |
| 4 | (0, 4) | [1, 2, 3, 3, 3] | [1, 2, 3, 3, 4] | [1, 2, 3, 2, 3] |
DP 最後呈現的DP周遊數組和方法一是一緻的：
DP二維矩陣1
| 1 | 2 | 3 | 4 | |
| 1 | 2 | 3 | 3 | 4 |
| 1 | 1 | 2 | 2 | 3 |
| 2 | 1 | 1 | 3 | |
| 3 | 1 | 1 | ||
| 4 | 1 |
方法三：倒序周遊
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
n = len(s)
dp = [[0]*(n) for i in range(n)]
for i in range(n):
dp[i][i] = 1
for i in range(n-2,-1,-1):
for j in range(i+1,n):
if s[i] == s[j]:
dp[i][j] = dp[i+1][j-1]+2
else:
dp[i][j] = max(dp[i+1][j],dp[i][j-1])
return dp[0][n-1]
方法四：基于倒序的狀态壓縮
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
n = len(s)
dp = [1 for i in range(n)]
for i in range(n-2,-1,-1):
pre = 0 //1 外循環新觸發時元素的更新
for j in range(i+1,n):
tmp = dp[j] //2
if s[i] == s[j]:
dp[j] = pre + 2
else:
dp[j] = max(dp[j-1],dp[j])
pre = tmp //3
return dp[n-1]
已測試集‘bbbab'為例：
測試過程資料：
| i | j | tmp | dp | pre | pre-校準（換行時pre=0） | ||||
| 3 | 4 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 3 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 4 | 1 | 1 | 1 | 1 | 1 | 3 | 1 | 1 |
| 1 | 2 | 1 | 1 | 1 | 2 | 1 | 3 | 1 | |
| 1 | 3 | 1 | 1 | 1 | 2 | 2 | 3 | 1 | 1 |
| 1 | 4 | 3 | 1 | 1 | 2 | 2 | 3 | 3 | 3 |
| 1 | 1 | 1 | 2 | 2 | 2 | 3 | 1 | ||
| 2 | 2 | 1 | 2 | 3 | 2 | 3 | 2 | 1 | |
| 3 | 2 | 1 | 2 | 3 | 3 | 3 | 2 | 2 | |
| 4 | 3 | 1 | 2 | 3 | 3 | 4 | 3 |
DP最後呈現的形式和二維DP是一緻的：
DP二維矩陣2
| 1 | 2 | 3 | 4 | |
| 1 | 2 | 3 | 4 | 4 |
| 1 | 1 | 2 | 2 | 3 |
| 2 | 1 | 1 | 3 | |
| 3 | 1 | 1 | ||
| 4 | 1 |
總結：傳動DP轉移矩陣就不多說了，主要說下狀态壓縮的壓縮邏輯搜尋方法：
1、先基于老的dp矩陣，安裝逆序或者斜線方法列出完整的DP二維矩陣1，2
2、在建立壓縮過程，找到中間變量或者過程數組tmp，pre，下一步要求的dp[j]的三元素在狀态壓縮後可以獲得
| dp[i][j-1] | dp[i][j] |
| dp[i+1][j-1] | dp[i+1][j] |
3、尤其注意每次外循環新觸發時元素的更新