代码随想录算法训练营第六十天| LeetCode647. 回文子串、516.最长回文子序列

一、LeetCode647. 回文子串

题目链接/文章讲解/视频讲解：https://programmercarl.com/0647.%E5%9B%9E%E6%96%87%E5%AD%90%E4%B8%B2.html

状态：已解决

1.思路

这道题我只想出来了暴力解法，动规解法并没有想出来。根据视频讲解才把它想出来。

（1）确定dp数组以及下标含义：

本题如果定义dp[i] 为下标i结尾的字符串有 dp[i]个回文串的话，我们会发现很难找到递归关系。那要怎么确定dp数组呢？根据回文串的性质：

当我们已知s[1]，s[2]，s[3] 这个子串是回文的，那么只需要比较 s[0]和s[4]这两个元素是否相同，如果相同的话，这个字符串s 就是回文串。也就是说，当确定一个范围是回文串时，我们就要确定这个范围向外面延申的两头是不是相等的，限定范围需要起点和终点，故dp数组应该是二维的：回文串的下表范围[i,j]，则判断子字符串（下表范围[i + 1, j - 1]））是否是回文。

故dp数组定义为：dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。

（2）确定递推公式：

确定递推公式时，由于要考虑 i+1 和 j-1 的边界问题，需要分析如下几种情况：

当s[i]与s[j]不相等，dp[i][j]一定是false。

当s[i]与s[j]相等时，这就复杂一些了，有如下三种情况

情况一：下标i 与 j相同，同一个字符例如a，当然是回文子串
情况二：下标i 与 j相差为1，例如aa，也是回文子串
情况三：下标：i 与 j相差大于1的时候，例如cabac，此时s[i]与s[j]已经相同了，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看dp[i + 1][j - 1]是否为true。

（3）初始化dp数组：

因为值都会被覆盖，且不可能初始化true（一开始全部都为回文串了，后面无论怎么判断也都会是true），故统一初始化为false。

（4）确定遍历顺序：

根据递推公式，情况三是根据dp[i + 1][j - 1]是否为true，来判断dp[i][j]是否为true的，故需要确定左下角的值，因此遍历顺序应该是从下到上、从左到右。（或者以列遍历）

（5）举例推导dp数组：

举例，输入："aaa"，dp[i][j]状态如下：

2.代码实现

class Solution {
public:
    int countSubstrings(string s) {
        vector<vector<bool>> dp(s.size(),vector<bool>(s.size(),false));
        int result = 0;
        for(int i=s.size()-1; i>=0; i--){
            for(int j=i;j<s.size();j++){ //根据区间定义，i必须比j小.
                if(s[i] == s[j]){
                    if(j-i<=1){
                        result++;
                        dp[i][j] = true;
                    }else if(dp[i+1][j-1]){
                        result++;
                        dp[i][j] = true;
                    }
                }
            }
        }
        return result;
    }
};

时间复杂度：O(n^2)

空间复杂度：O(n^2)

二、516.最长回文子序列

题目链接/文章讲解/视频讲解：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

状态：已解决

1.思路

这题比上道题简单一点，因为求的是回文子序列不要求连续了。

（1）确定dp数组以及下标含义：

dp[i][j]：字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。

（2）确定递推公式：

还是分两种大情况：

① 如果s[i]与s[j]相同，那么dp[i][j] = dp[i + 1][j - 1] + 2;

② 如果s[i]与s[j]不相同，说明s[i]和s[j]的同时加入并不能增加[i,j]区间回文子序列的长度，那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。

加入s[j]的回文子序列长度为dp[i + 1][j]。

加入s[i]的回文子序列长度为dp[i][j - 1]。

那么dp[i][j]一定是取最大的，即：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

（3）初始化dp数组:

首先要考虑当i 和j 相同的情况，从递推公式：dp[i][j] = dp[i + 1][j - 1] + 2; 可以看出递推公式是计算不到 i 和j相同时候的情况。所以需要手动初始化一下，当i与j相同，那么dp[i][j]一定是等于1的，即：一个字符的回文子序列长度就是1。

其他情况dp[i][j]初始为0就行，这样递推公式：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); 中dp[i][j]才不会被初始值覆盖。

这里我为了提高效率就把初始化定义在递推公式的循环里面了。

（4）确定遍历顺序：

从递归公式中，可以看出，dp[i][j] 依赖于 dp[i + 1][j - 1] ，dp[i + 1][j] 和 dp[i][j - 1]，如图：

故要从下往上、从左到右。

（5）举例推导dp数组：

输入s:"cbbd" 为例，dp数组状态如图：

最后返回dp[0][s.size()-1]即可

2.代码实现

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        vector<vector<int>> dp(s.size(),vector<int>(s.size(),0));
        int length = 0;
        for(int i=s.size()-1; i>=0; i--){
            for(int j=i;j<s.size();j++){ //根据区间定义，i必须比j小.
                if(s[i] == s[j]){
                    if(j-i==0){
                        dp[i][j] = 1;
                    }else{
                        dp[i][j] =  dp[i+1][j-1]+2;
                    }
                }else{
                    dp[i][j] = max(dp[i+1][j],dp[i][j-1]);
                }
            }
        }
        return dp[0][s.size()-1];
    }
};