摘要

• 今天的两道题目是区间 dp 的入门题目，以每一个区间作为一个状态来定义 dp 数组和递推公式。
• 子串（子字符串）要求元素在原序列（原字符串）中连续，子序列不要求元素在原序列中连续，但元素在子序列和原序列中的相对顺序要相同。
• 子序列就要考虑不选择起点或终点的情况。

LeetCode647 回文子串

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

• 按以往的经验，可能会这样定义dp数组：
  • dp[i]表示从下标0到下标i的s的子字符串，包含的回文子串的个数是dp[i]。
  • 这样定义之后，很容易发现，递推公式很难推导。
  • 因为“回文子串”这个概念本身，就包含了对称性，需要从子串的起点和终点开始判断子串是否是回文。如果像上面那样定义dp数组，起点固定为下标0，显然忽略了起点的信息。
• 所以，dp数组应该同时考虑起点和终点的信息。
  • dp[i][j]表示以下标i为起点且以下标j为终点的s的子字符串是否是回文子串。
  • 终点下标应大于或等于起点下标，所以i <= j
• 推导递推公式，dp[i][j]的值有如下可能
  • 如果i == j，起点下标和终点下标相等，表示当前子串只有一个字符，只有一个字符的字符串是回文子串，所以
  • 如果s[i] == s[j]，要分两种长度来考虑
    1. j - i == 1，说明当前子串只有两个字符，这两个字符相等，当然是回文子串。
    2. j - i > 1，说明当前子串的字符数大于2，已知的是s[i] == s[j]，所以当前子串是不是回文子串取决于s[i+1] == s[j-1]、s[i+2] == s[j-2]等等是否成立，即取决于除去s[i]和s[j]的中间的那节子串是否是回文子串，即取决于dp[i+1][j-1]，
  • 如果s[i] != s[j]，当然不是回文子串，那就不用考虑了。
• 初始化dp数组，有两种方案
  • 将i == j的dp[i][j]初始化为true，其他初始化为false。
  • 全都初始化为false，在dp数组的计算过程中顺便考虑i == j的情况。
  • i == j时自然有s[i] == s[j]，所以i == j也可以归入到s[i] == s[j]的第一种情况。选择第二种方案，代码较简洁。
• 遍历顺序，dp[i][j]的更新依赖于dp[i+1][j-1]
  • 所以i应该从大到小遍历，j应该从小到大遍历，另外，j >= i，所以j应该从i开始。

题解代码如下，在计算dp数组的同时计算回文子串的个数，保存在res中。

class Solution {
public:
    int countSubstrings(string s) {
        vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));

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

        return res;
    }
};

LeetCode516 最长回文子序列

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

• 这道题和上一题相比，有两个地方变复杂了

  • 一是要求的是子序列，元素可以不连续
  • 二是要求的是长度，不是仅仅判断是否是回文

• dp数组及数组下标的含义：起点下标为i且终点下标为j的s的子序列，包含的最长的回文子序列的长度为dp[i][j]。

• 递推公式：

  • 如果s[i] == s[j]
    1. 如果j == i，s[i] == s[j]自然成立，[i, j]内唯一可能的子序列就是只有一个字符的子序列，只有一个字符的子序列是回文子序列，所以
    2. 如果j - i == 1，[i, j]内可能的子序列最多包含两个字符，可能的最长回文子序列就是{s[i], s[j]}。所以
    3. 如果j - i > 1，[i, j]内可能的最长回文子序列的长度要取决于之前求得的最长回文子序列，即不考虑s[i]和s[j]的最长回文子序列的长度，即dp[i+1][j-1]。
  • 如果s[i] != s[j]
    1. 不选择s[i]，那么最长回文子序列的长度为dp[i+1][j]
    2. 不选择s[j]，那么最长回文子序列的长度为dp[i][j-1]
    3. s[i]和s[j]都不选择，这种情况已经被以上两种情况覆盖。

• 初始化dp数组，全都初始化为0，j - i <= 1的情况也统一放在dp数组的计算中

  • s[i]==s[j]且j - i <= 1时，dp[i][j] = j - i + 1

• 遍历顺序，和上一题一样，i从大到小，j从小到大

题解代码如下

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