算法随想Day50【动态规划】| LC647-回文子串、LC516-最长回文子序列

LC647. 回文子串

动态规划法：

遍历顺序：从下往上，从左往右

当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。

int countSubstrings(string s)
{
    int size = s.size();
    int count = 0;
    vector<vector<bool>> dp(size, vector<bool>(size, false));
    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)
                {
                    ++count;
                    dp[i][j] = true;
                }
                else if (dp[i + 1][j - 1] == true)
                {
                    ++count;
                    dp[i][j] = true;
                }
            }
        }
    }
    return count;
}

中心拓展法：

int countSubstrings(string s)
{
    int size = s.size();
    int count = 0;
    for (int i = 0; i < size; ++i)
    {
        count += extend(s, i, i, size);
        count += extend(s, i, i + 1, size);
    }
    return count;
}
int extend(const string& s, int left, int right, int size)
{
    int ret = 0;
    while (left >= 0 && right <= size - 1 && s[left] == s[right])
    {
        --left;
        ++right;
        ++ret;
    }
    return ret;
}

LC516. 最长回文子序列

有了上一题的基础，起码知道如何列dp二维矩阵了

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

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