小Tips

1. 每次的方案是枚举一个排列,可以考虑以排列的长度作为一维
   377. 组合总和 Ⅳ
   343. 整数拆分
   279. 完全平方数

2. 在环形上DP,可以考虑把求值范围切成两段或者说把数组复制一遍
   918. 环形子数组的最大和

3. 可以把题目中带有后效性的转移 转变成不带有后效性的转移
   740. 删除并获得点数
   如果直接以nums[i]来枚举计算状态,显然没办法直到下一次会转移到哪个状态
   但是如果以数字大小来枚举,那么就变成了i-1 i i+1之间的依赖

   实际上对于i-1 i i+1这种连续依赖只需要考虑“当前数”与“前一个数”的关系即可，这样处理完，显然每个数的「前一位/后一位」都会被考虑到。注意：这种关系必须是可传递的

回文序列

判断方法

普通判断:
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找到的不是同一段位置的