动态规划解决leetcode上的两道回文问题（针对思路）

本期主讲的是使用动态规划去解决两道回文问题，分别是

647. 回文子串 - 力扣（LeetCode）

516. 最长回文子序列 - 力扣（LeetCode）

而不是leetcode5.最长回文子串，虽然这道题也是回文问题，也可以使用dp来解决，但是这道题本人认为与647回文子串思路相同，但这里也给出大致的解题思路。

这道题求的是连续子数组问题，而且是最长的回文的子数组，虽然它只有一个字符串，但是我们也使用二维dp数组，一维代表起始子数组，另一维是标识该子数组的终点，然后从后往前遍历字符串，两层循环，分别指子串起始和末尾，然后判断当前两个下标对应字符是否相等，然后再看中间的子数组是否回文，若是则更新答案。

这道题的思路其实就是我们要讲的回文子串的思路，只不过处理数据有些不同而已，求最长子数组就是记录当前多长，和之前的比较。而这道记录的是有多少回文子串，实际思路是相同的

---

第一道题 

先看代码：

class Solution {
public:
    int countSubstrings(string s) {
        int n=s.size();
        vector<vector<bool>>dp(n,vector(n,false));int res=0;
        for(int i=n-1;i>=0;--i){
            for(int j=i;j<n;++j){
                if(s[i]==s[j]){
                    if(j-i<=1){dp[i][j]=true;++res;}
                    else if(dp[i+1][j-1]){dp[i][j]=true;++res;}
                }
            }
        }
        return res;
    }
};

 我们以一个布尔类型二维数组做判断，循环就是刚才说的，从后往前，为什么从后往前，这是因为递推式的缘故，我们要判断当前字符相等的情况下，看一看该子串里面的内容是否回文，怎么看？它是比较i+1和j-1，所以一定要保证这一段已经被判断回文过了，所以我们才会选择从后往前遍历的方法，而内层循环你看着可能有些奇怪，但事实上它是正确的。因为如果两个下标对应相等还存在两种情况，一种是两下标指向同一字符，此时肯定回文，另一种是指向不同字符，但是这两个下标只差1，也就是说【a】和【aa】这两种情况的对应。我们都考虑了进来，当两下标相差大的时候，里面就会存有子数组我们才会进行判断，而此时判断的话，已经是之前遍历过的位置了，已经知道了它回不回文。

可能有读者会问，是否可以从字符串中间去进行向两边扩散的访问，以得到是否回文的情况，这一招很好用，对于判断整个字符串是否回文，以及判断整个字符串的最长回文子数组的长度，但是并不适用于本题，因为本题求解的是根据每一个下标的情况给出可能存在的所有回文的子数组的个数

而上面的那招中心探测，并不完全，如果使用中心探测至少要对每个子串都进行回文判断，所以无论如何你都逃脱不了，要判断每个子串的命运，而不是只在字符串的中心位置判断回文，而只On就能解决问题，你最少需要ON^2才可以解决问题。（至少我知道的方法里没有ON）

当然如果你是算法老鸟，你可以对二维数组进行一维的压缩，以解决减少时间复杂度的开销，但是通常我只会在简单的题解里才会想这种优化，稍稍复杂一点的题解，很容易出现各种问题，所以我一般倾向于解题，而不是给自己找麻烦。

---

第二道题

 最长回文子序列，是不是看起来和那道最长回文子串差不多，这道题只不过是求不连续的子序列最长的长度。

但我们这里的思路并不沿用上面的思路。尽量不要使用回文子串那道题目的做法，会使得代码难写且含义不清晰，因为那道做法dp含义是针对于连续子数组的，我们很难只用true或false来判断中间字符串的回文长度到底为多少，而且在本题中，这样的bool数组并没有太多价值，因为如果要存子序列的最长数多半情况是用到其他变量辅助存储的，而bool数组起到的作用只是判断这段子数组是否回文，与这道题实际的问题有点相违背。

这道题我们采用如下的思路：

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n=s.size();
        vector<vector<int>>dp(n,vector(n,0));
        for(int i=0;i<n;++i)dp[i][i]=1;
 
        for(int i=n-1;i>=0;--i){
            for(int j=i+1;j<s.size();++j){
                if(s[i]==s[j])dp[i][j]=dp[i+1][j-1]+2;
                else dp[i][j]=max(dp[i][j-1],dp[i+1][j]);
            }
        }
        return dp[0][n-1];
    }
};

 dp数组的含义代表当前ij范围内最长的回文子序列多长，子序列可以不连续
当此时ij对应下标字符相等，则用两下标中间的子串范围的最大回文子序列长度+2，也就是把s【i】和s【j】都加入进来
如果此时不相等，则判断如果只加进一个能否取得最长回文子序列，也就是说dp【i】【j-1】和dp【i+1】【j】它们两个比较然后取最大值。
为什么这样呢？因为s【i】和s【j】中间的子数组应该是以s【i+1】和s【j-1】为下标的，所以左边加进来s【i】就是dp【i】【j-1】右边加进来j就是dp【i+1】【j】
别忘了根据递推式的含义，最后返回的应该是dp【0】【s.size（）-1】
代表从0开始到结束最长的回文子序列

是不是有疑问了？为什么这道题的内部循环变得更奇怪了？要使用j=i+1的初始化，这样不会越界吗？

接下来我们来解释一下这样做的原因。

里层循环i+1，并不是无用的，不能设置为j=i
有两个原因一个是浅显易见的，是因为两个下标指向同一字符的情况我们已经初始完毕了，另一原因是如果从j=i进来那第一次填数会导致数组非法下标访问，而第二次进来虽然推导时候也有些奇怪，因为i和j拉开距离过小的缘故，i会走到j的位置，也就是i上一次遍历的位置，j会走到i本次起始遍历位置，虽然奇怪，但是也是遍历过的，所以答案也是对的。

没错前面的循环是为了初始化，因为至少它的最长回文子序列一定是1，我们要把它初始化一下，这也方便接下来dp数组的正确填数。而由于递推式的缘故，我们也不能使内层循环写成j=i开始，要不然一开始就会越界，这道题不像上一道题，上一道题是极可能存在相邻两个相等的情况，而且那道题的dp数组含义也与本题不同。那道题j=i的初始化由于前面的if判断，j<=i的时候会有一个缓冲，不会过早进到中间子数组的判断，这道题递推式不行，它不具备那样的缓冲。

那我们可以加一个那样的判断吗？判断两字符相等且j<=I然后填数做缓冲不就可以了吗？

好问题，可以

但是求子序列的含义是我们可以允许不相邻的子序列也构成答案，也就是说子序列答案是包含了两个字符相邻回文，也就是子序列包含子数组的所有情况，没必要写一个特式专门用来判断这一步骤，这显得有点繁琐了，子序列的代码应该更适用于大多数的情况。

但如果加一步那样的判别可以使一开始的判断回文看起来正常一些，j也不用从i+1开始判断了，也是一种好的题解思路。

那这道题可以从字符串中间进行下标的开始匹配吗？我认为有点问题，类中心探测法无论是一次匹配还是每个字符的分别匹配，本质上都是用来解决连续的子数组的问题，用在子序列可能有点麻烦，我没有试过，感兴趣的读者可以自己试一下。我认为应该有点难度。

---

都看到这里了如果对您有用的话别忘了一键三连哦，如果是互粉回访我也会做的！

大家有什么想看的题解，或者想看的算法专栏、数据结构专栏，可以去看看往期的文章，有想看的新题目或者专栏也可以评论区写出来，讨论一番，本账号将持续更新。
期待您的关注