代码随想录 11.17 || 动态规划 LeetCode 647.回文子串、516.最长回文子序列

647.回文子串

        给你一个字符串 s，请你统计并返回这个字符串中 回文子串 的数目。回文字符串 是正着读和倒过来读一样的字符串。子字符串 是字符串中由连续字符组成的一个序列。具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

        求回文字符串中，回文子串的数量。设 i ~ j 表示字符串 s 以下标 i 开始和 j 结尾的字符子串，设该子串为回文串，如何转移状态至下一个子串，下一个子串该如何定义？

        我们定义 dp[ i ][ j ] 为以字符 i 开头和以字符 j 结尾的字符子串是否为为回文串 true or false；

        如果 s[ i ] == s[ j ]，表明字符在 i 和 j 处相同，此时有三种情况，情况 1，i 和 j 指向同一个字符，相邻距离为 0；情况 2，i 和 j 距离为 1，且指向的字符相同。上面两种情况下，该区间内的字符子串都是回文串，递推公式为 dp[ i ][ j ] = true。情况 3，i 和 j 的距离相差大于 1，此时二者指向的字符串中间存在若干字符串，所以当前字符串是否为回文串取决于前一个字符串是否为回文串，递归公式为，if (dp[i + 1][j - 1]) dp[ i ][ j ] = true；

        遍历顺序，从递推公式中可知，任意取字符串 s 的 i 和 j 区间（j >= i），该字符子串是否为回文串取决于字符子串 i + 1，j - 1是否回文。体现在 dp 数组中，为从左下向右上遍历；

        初始化，全 false；

        打印 dp 数组，debug。

516.最长回文子序列

        本题与上一题思路相似，区间 [i, j] 内的字符子串最长回文子序列的长度取决于区间 [i + 1, j - 1] 内字符子串最长回文子序列的长度。因此，定义 dp[i][j] 为在区间 [i, j] 最长回文子序列的长度。递推公式为，如果 s[i] == s[j]，则 dp[i][j] = dp[i + 1][j - 1] + 2，当前区间内最长回文子序列的长度 = 前一个区间内最长回文子序列的长度 + 2；如果不满足相等条件，则 dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])，当前区间内最长回文子序列的长度取决于不考虑 i 或者 j 的字符子串内的最长回文子序列的长度。

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int len = s.size();

        auto dp = vector<vector<int>> (len, vector<int> (len, 0));
        for (int i = 0; i < len; ++i) dp[i][i] = 1;

        for (int i = len - 1; i >= 0; i--) {
            for (int j = i + 1; j < len; 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][len - 1];
    }
};