回文序列

判断方法

普通判断:
1.从中间向两边走,分别匹配元素或者从两边往中间走,分别判断两边元素是否相等
2.将序列翻转,然后与原序列比较

解题思路

从判断方法1出发

s[i~j]是否为回文串即可用判断s[i]==s[j]&&f[i+1][j-1]来判断
如果s[i]!=s[j]那么显然不是一个回文串,如果s[i+1~j-1]不是一个回文串,那么s[i~j]显然也不是一个回文串

s[i~j]是否为回文子序列,即可用判断s[i]==s[j]||s[i+1][j-1]||f[i][j-1]||f[i+1][j]来判断
如果s[i]!=s[j]那么显然不是如果回文子序列包含端点,那一定只包含一个,所以是f[i+1][j],f[i][j-1]

从判断方法2出发

如果想要找最长回文序列，根据普通的判断2就可以知道应该是原序列和反转序列求最大公共子序列

如果想要找最长回文子串，根据普通的判断2就可以知道应该是原序列和反转序列求最大公共子串(转化为bool而不是int)

是因为如果要求是子串的话,直接使用最长公共子序列可能导致s1与s2找到的不是同一段位置的