647. 回文子串

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

思路：

dp数组：布尔类型的dp[i][j]：表示区间范围[i,j] （左闭右闭）的子串是否是回文子串。j 必然大于等于 i，因此dp数组右上三角才有意义。初始化为False。

递推公式：当s[i]与s[j]不等时，False。当s[i]与s[j]相等时，有如下三种情况：情况一：下标i 与 j相同，同一个字符，当然是回文子串，对角线。情况二：下标i 与 j相差为1，例如aa，也是回文子串，对角线右上方的斜线。情况三：下标：i 与 j相差大于1的时候，既然首尾两个元素相同，那只要看 i+1 到 j-1区间，dp[i][j] = dp[i + 1][j - 1]。

遍历顺序：从递推公式看，左下角的元素决定右上角的元素。因此上往下，从左往右遍历。

516.最长回文子序列

给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。

思路：

dp数组：dp[i][j]：字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。同样只有dp数组右上三角才有意义。对角线初始化为1，其他初始化为0。

递推公式：当s[i]与s[j]不等时，回文子序列长度没有增加，但也没有减少，因此 dp[i][j] = max(dp[i][j-1], dp[i+1][j])。当s[i]与s[j]相等时，回文子序列头尾各加一，因此长度是dp[i][j] = dp[i+1][j-1] + 2。

以下是卡哥资料

 647. 回文子串   

动态规划解决的经典题目，如果没接触过的话，别硬想 直接看题解。

https://programmercarl.com/0647.%E5%9B%9E%E6%96%87%E5%AD%90%E4%B8%B2.html 

 516.最长回文子序列 

 647. 回文子串，求的是回文子串，而本题要求的是回文子序列， 大家要搞清楚两者之间的区别。 

https://programmercarl.com/0516.%E6%9C%80%E9%95%BF%E5%9B%9E%E6%96%87%E5%AD%90%E5%BA%8F%E5%88%97.html 

 动态规划总结篇 

https://programmercarl.com/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E6%80%BB%E7%BB%93%E7%AF%87.html