代码随想录算法训练营Day57|647. 回文子串、516.最长回文子序列、动态规划总结

647. 回文子串

前言

思路

算法实现

516.最长回文子序列

前言

思路

算法实现

动态规划总结

动规五部曲回顾

动规各小专题问题

647. 回文子串

题目链接

文章链接

前言

本题利用动态规划求解时，dp数组的定义与前面的就有些不同了，是难点之一。

思路

本题利用动态规划的方法进行求解：

1.确定dp数组及其下标的含义：

如果按照前面做题的思路将dp数组的定义设置为dp[i] 为下标i结尾的字符串有 dp[i]个回文串的话，很难找到递推关系。

因此本题要根据回文子串的性质来确定dp数组：

在判断字符串s是否回文时，只要知道s[1]，s[2]，s[3] 这个子串是回文的,那么只需要比较 s[0]和s[4]这两个元素是否相同，如果相同的话，这个字符串s 就是回文串。

此时就找到了一种递归关系，也就是判断一个子字符串（字符串的下表范围[i,j]）是否回文，依赖于，子字符串（下表范围[i + 1, j - 1]））是否是回文。

所以为了明确这种递归关系，我们的dp数组是要定义成一位二维dp数组。

布尔类型的dp[i][j]：表示区间范围[i,j] （左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。

2.确定递推公式

整体上是两种情况，就是s[i]与s[j]相等，s[i]与s[j]不相等这两种。

s[i]与s[j]不相等时，dp[i][j]就是false；

s[i]与s[j]相等时，又分为三种情况：

情况一：下标i与j相同时，此时为同一个字符，必然是回文子串；

情况二：下标i与j相邻时，此时也是回文子串；

情况三：下标i与j不相邻时，要看是s[i]之后和s[j]之前的部分是否是回文子串，若是则算上s[i]、s[j]也为回文子串；

在每种情况中对应统计回文子串的数目result；

3.初始化dp数组：

一开始将dp[i][j]全部初始化为false，否则对后面的判断是否为回文子串有影响；

4.确定遍历顺序：

首先从递推公式中可以看出，情况三是根据dp[i + 1][j - 1]是否为true，在对dp[i][j]进行赋值true的。dp[i + 1][j - 1] 在 dp[i][j]的左下角，如图：

遍历顺序是从左到右，从下到上。

5.打印dp数组：

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

图中有6个true，所以就是有6个回文子串。

算法实现

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++) {
                if (s[i] == s[j]) {
                    if (j - i <= 1) {
                        dp[i][j] = true;
                        result++;
                    }
                    else if (dp[i + 1][j - 1] == true) {
                        dp[i][j] = true;
                        result++;
                    }
                }
            }
        }
        return result;
    }
};

516.最长回文子序列

题目链接

文章链接

前言

上一题要求的是连续的回文子串，本题求最长回文子序列就没有了连续的要求。

思路

依然是利用动规五部曲进行分析：

1.确定dp数组及其下标的含义：

dp[i][j]：字符串s在下标在[i, j]范围内的最长回文子串长度为dp[i][j]；

2.确定递推公式：

还是分s[i]和s[j]相等和不等两种情况进行讨论：

当s[i]和s[j]相等时，回文子序列长度加2，dp[i][j] = dp[i + 1][j - 1] + 2;

当s[i]和s[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数组：

从递推公式：dp[i][j] = dp[i + 1][j - 1] + 2; 可以看出递推公式是计算不到 i 和j相同时候的情况，因此需要进行手动初始化，当i与j相同，那么dp[i][j]一定是等于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]; 为最终结果。

算法实现

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        vector<vector<int>> dp(s.size(), vector<int> (s.size(), 0));
        for (int i = 0; i < s.size(); i++) dp[i][i] = 1;
        for (int i = s.size() - 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 + 1][j], dp[i][j - 1]);
            }
        }
        return dp[0][s.size() - 1];
    }
};