最长回文子序列

*************

C++

题目来源：516. 最长回文子序列 - 力扣（LeetCode）

*************

看一下题目

这个让我想到前几天做过的最长回文子串，那个简单的中心拓展法我不会，头铁做成了dp数组，有点忘了，重新做一下。

最长回文子串的题目是：给定一个字符串 s ，找出其最长的回文子串。简单地找到两个字母组成的子串就是比较 bool (dp[i], dp[i + 1])，

for (int len = 3; len <= n; len++) { // assume only 3 elements in the string
            for (int i = 0; i < n - len + 1; i++) { // 
                int j = i + len - 1; // assume the last element
                if (s[i] == s[j] && dp[i + 1][j - 1]) {
                    dp[i][j] = true;
                    longest = s.substr(i, len);
                }
            }
        }

回到题目，那就可以按照这个逻辑，在原有的基础上开始优化。这个像模糊拼音输入法的逻辑。就好像我想打的这个，实际上， jiuhaoxing 可能是 jiuhaoxiang 或则 jiuhaoxig，都能打出就好像。

到这里，就大概知道了这个题目在生活中的应用了。

起手也是正常的获得字符串 s 的长度，初始化一个dp数组用于存储新的寻找下来的序列串。

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.size(); // get the length of the string
        vector<vector<int>> dp(n, vector<int>(n, 0)); // initialise the array into elements zero
};

接下来我会用上我的老朋友，矩阵，来帮我理解接下来的代码顺序。我喜欢在在工作的时候碎碎念，这样会帮助我理清思路。假如我是计算机，我获得了一组字符串，

s = "apple"

首先 n = 5；这一步很简单，一共五个字母，熟悉十以内加减法的人都知道。

初始化矩阵，并且矩阵中所有的元素都为 0；

定义 dp[i][i] = 1，这个很简单，因为只包含1个字母的字符串肯定是回文。

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.size(); // get the length of the string
        vector<vector<int>> dp(n, vector<int>(n, 0)); // initialise the array into elements zero

        for (int i = 0; i < n; i++){
            dp[i][i] = 1; // ez to understand that one letter is always true
        }
};

第二步就是，找到2个字母的回文串。这个的判断很简单，就是s[i] == s[i + 1]。

• 检查 s[0] 和 s[1]，它们是 'a' 和 'p'，不相等，所以 dp[0][1] = max(dp[1][1], dp[0][0]) = max(1, 1) = 1。
• 检查 s[1] 和 s[2]，它们是 'p' 和 'p'，相等，所以 dp[1][2] = max(dp[2][2], dp[1][1]) = max(3, 1) = 3。
• 检查 s[2] 和 s[3]，它们是 'p' 和 'l'，不相等，所以 dp[2][3] = max(dp[3][3], dp[2][2]) = max(1, 3) = 3。
• 检查 s[3] 和 s[4]，它们是 'l' 和 'e'，不相等，所以 dp[3][4] = max(dp[4][4], dp[3][3]) = max(1, 3) = 3。

这里得重申一下 dp[s][m] 的概念，这里是以字符串中 s 为起点， m 为终点的字符串中，可以组成回文的字符串长度。

这里是比较难理解的，好在我还会一个东西，就是举例子，穷举美学，我的apple。

既然 dp[s][m] 表示 s()中，第s位到第m位，这里规定一下m ＜ s，顺便普及一个冷知识， s的全拼是 sadism，并且m 的全拼是 masochism，简单地学习两个英文单词。

假如，已知 dp[s + 1][m - 1] 是回文子串，注意这里是串，串不可以增加或者减少元素，

那么我就要知道dp[s][m] = dp[s + 1][m - 1] + 2，因为是长度，首尾各加一个字母。

还是以 s = "apple" 举例，我看得出来 这个有一个回文是 ss

如果 length = 2，也就是说dp[1][2] = 2，那么，我就要看一下s[0] != s[3]，这里显然 a != l的值是false，也就是说dp[0][3] = 2，穷举美学来了，既然dp[0][3] = 2，那我观察一下s[0] != s[2]，这里等价于dp[0][2]，显然s[0] != s[2]是false，向左穷举美学不美，向右试一试，s[1] != s[3]的值也是false，因为p ≠ l。

这里定义一个指针i，从以一个元素开始遍历， j =  i + length - 1，目的是保证所有的串都能烤到。以 length = 2 开始，

i = 0； length = 2; j = 1; s = {a, p}; 不是回文；接着问；

i = 1； length = 2; j = 2; s = {p, p}; 是回文；进入循环， if {s[1] == s[2]}，那就 dp[1][2] = dp[2][1] + 2，这个显然是不对的， 因为设置的i < j，所以要加一个判断条件，新赋值的 {i + 1 <= j - 1 ?},这句话的意思代表  {i + 1 <= j - 1是对的吗？}  显然这里不是，因此要进入判断了，dp[1][2] = max(dp[2][2], dp[1][1])；继续循环；

i = 1； length = 3; j = 3; s = {p, p, l}; s[1] ≠ s[3]，dp[1][3] = max(dp[1 + 1][3], dp[1][3 - 1])

i = 1； length = 4; j = 4; s = {p, p, l, e}; s[1] ≠ s[4]，dp[1][4] = max(dp[1 + 1][4], dp[1][4 - 1])

总结：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])

因此可以把最重要的代码写出来了：

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.size(); // get the length of the string
        vector<vector<int>> dp(n, vector<int>(n, 0)); // initialise the array into elements zero

        for (int i = 0; i < n; i++){
            dp[i][i] = 1; // ez to understand that one letter is always true
        }

        // caculate the length more than 2
        for (int len = 2; len <= n; ++len) { // out-cicle is the length of the new string
            for (int i = 0; i <= n - len; ++i) { // in-cicle start from the different place
                int j = i + len - 1; // define the end of the string
                if (s[i] == s[j]) { // in new srtring, stare == end, which has the possibility, so need check
                    dp[i][j] = (i + 1 <= j - 1 ? dp[i + 1][j - 1] : 0) + 2;
                } else {
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        
        // dp[0][n-1] return
        return dp[0][n - 1];
    }
};

这里举例子的暴力美学就在于，所有的情况都被考虑到了。

length = 1 ~ n; 

这里一个很重要的想法是，在计算dp[i][j]的时候，先判断s[i] = s[j] ？，如果是，那就是一个崭新的回文子串，直接 dp[i][j] = dp[i + 1][j - 1] + 2, 那如果不是，那就是掐头或者祛尾的那个较大的值。

最后的最后，周五了，又活了一周，真的很棒。

周末快乐。