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

647.回文子串

代码随想录链接

题目

LeetCode-647.回文子串

根据给定的字符串计算这个字符串里有多少回文子串.

题目分析

动态规划五部曲:

• 确定dp数组及下标的含义

  如果规定dp[i]是以下标i为结尾的字符串有dp[i]个回文串的话, 会发现dp[i], dp[i-1], dp[i+1]之间没有什么关系, 这就不符合动态规划的条件了.

  由回文串的性质可知, 如果s[i, j]区间的子串是回文串的话, 那么如果s[i-1]==s[j+1], 则s[i-1. j+1]也一定是回文串, 故可以有dp[i][j]表示s[i, j]之间的字符能够形成回文串与否.

• 确定递推公式

  如果s[i] != s[j], 则dp[i][j]一定是false;

  若s[i] == s[j],

  1. 若i == j, 即同一个字符, 是回文串, dp[i][j] = true;
  2. 若i != j, 但 j - i = 1, 即相邻字符相等, 则也是回文串, dp[i][j] = true;
  3. 若i != j, 且 i 与 j相差超过1, 则需要看dp[i+1][j-1]是否为回文串, 即dp[i][j] = dp[i + 1][j - 1];

• dp数组的初始化

  全部初始化为false.

• 遍历顺序

  由递推公式知, dp[i][j]会由左下角的值推出, 故应当外围for循环从后向前, 内层for循环从前向后.

题解

动态规划:

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

双指针法:

class Solution {
private:
    int extend(const string &s, int i, int j) {
        int res = 0;
        while (i >= 0 && j < s.size() && s[i] == s[j]) {
            i--; j++; res++;
        }
        return res;
    }
public:
    int countSubstrings(string s) {
        int result = 0;
        for (int i = 0; i < s.size(); i++) { // 从给定的字符开始, 双指针向左向右展开, 寻找以给定的一个或两个字符为中心的字符串是否为回文串
            result += extend(s, i, i);
            result += extend(s, i, i + 1);
        }
        return result;
    }
};

516.最长回文子序列

代码随想录链接

题目

LeetCode-516.最长回文子序列

从给定的字符串中找出最长的回文子序列, 返回其长度.

题目分析

动态规划五部曲:

• 确定dp数组及下标的含义

  dp[i][j]表示s[i, j]范围内最长的回文子序列的长度为dp[i][j].

• 确定递推公式

  如果s[i] == s[j], 则dp[i][j] = dp[i + 1][j - 1] + 2;

  如果s[i] != s[j], 则尝试让s[i] 和 s[j] 分别加入 s[i + 1, j - 1]的序列中, 求回文子序列的最大长度, 即dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]).

• dp数组的初始化

  二维数组正对角线上的值全部初始化为1, 其余部分为0.

• 遍历顺序

  由递推公式知, dp[i][j]的来源状态有dp[i + 1][j - 1], dp[i][j - 1], dp[i + 1][j]. 故遍历顺序一定是从下往上, 从左向右.

题解

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][j - 1], dp[i + 1][j]);
        return dp[0].back();
    }
};

动态规划总结篇

代码随想录链接

最重要的:

动态规划五部曲:

• 确定dp数组及下标的含义
• 确定递推公式
• dp数组的初始化
• 遍历顺序
• 举例推导