动态规划-区间DP-最长回文子序列

Posted by

定义

最长回文子序列(Longest Palindromic Subsequence): 一个串的所有回文子序列中最长的一个。

注意和最长回文子串的区别。

求解算法

思路

区间DP:设$a[1\ldots n]$表示原序列,$f[i][j] $为$a[i…j] $的最长回文子序列。

状态转移方程:

$$
f[i][j]=
\begin{cases}
f[i+1][j-1]+2,\quad a[i]=a[j] \\
max(f[i+1][j],f[i][j-1]),\quad a[i]\neq a[j]
\end{cases}
$$

边界条件:当$i=j $时,$f[i][j]=1 $。

显然答案为$f[1][n] $。

实现

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注