Longest Palindromic Substring
Given a string s, find the longest palindromic subsequence’s length in s. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. Example 1: Input: s = “bbbab” Output: 4 Explanation: One possible longest palindromic subsequence is “bbbb”. Example 2: Input: s = “cbbd” Output: 2
Example 1: Input: s = “bbbab” Output: 4 Explanation: One possible longest palindromic subsequence is “bbbb”.
Example 2: Input: s = “cbbd”
Output: 2 Explanation: One possible longest palindromic subsequence is “bb”.Explanation: One possible longest palindromic subsequence is “bb”.
Constraints: 1 <= s.length <= 1000 s consists only of lowercase English letters.
题目要求找到一个字符串 s 中最长的回文子序列然后返回长度，子序列是通过不改变字符的相对顺序，删除某些字符或者不删除任何字符形成的，回文子序列是一个正读和反读相同的子序列。
Tag打了动态规划，两种方式：递归和递推，就拿递归做入口了。
首先初始化一个二维数组dp来表示表示字符串区间 s[i] 到 s[j] 之间的最长回文子序列的长度，最初这里所有的 dp[i][j] 初始值设为 0。
当只考虑一个字符的情况下，它本身就是一个回文子序列，所以对于每个 i，都可以将 dp[i][i] 设为 1来表示字符串中单个字符是长度为 1 的回文子序列。
通过两个字符的比较来扩展回文子序列的长度可以分为以下两种情况：
-
s[i] == s[j]： s[i] 和 s[j] 相等时可以成为回文子序列的两端，那么回文子序列的长度就是 s[i+1] 到 s[j-1] 这段字符串的最长回文子序列的长度加上 2，递推关系为：dp[i][j] = dp[i+1][j-1] + 2
-
s[i] != s[j]： s[i] 和 s[j] 不等时s[i] 和 s[j] 就不能同时出现在同一个回文子序列中。这个时候有两个选择：丢弃 s[i]or丢弃 s[j]，然后再在剩下的部分中找最长的回文子序列；比较 s[i+1] 到 s[j] 和 s[i] 到 s[j-1] 两段字符串中的最长回文子序列的长度，取两者中的较大值作为当前区间的最长回文子序列长度。递推关系为：dp[i][j] = max(dp[i+1][j], dp[i][j-1])
maximize palindrome length from subsequences
You are given two strings, word1 and word2. You want to construct a string in the following manner:
Choose some non-empty subsequence subsequence1 from word1.Choose some non-empty subsequence subsequence1 from word1.
Choose some non-empty subsequence subsequence2 from word2.
Concatenate the subsequences: subsequence1 + subsequence2, to make the string. Return the length of the longest palindrome that can be constructed in the described manner. If no palindromes can be constructed, return 0.
A subsequence of a string s is a string that can be made by deleting some (possibly none) characters from s without changing the order of the remaining characters.
A palindrome is a string that reads the same forward as well as backward.
Example 1:
Input: word1 = “cacb”, word2 = “cbba” Output: 5 Explanation: Choose “ab” from word1 and “cba” from word2 to make “abcba”, which is a palindrome.
Example 2:
Input: word1 = “ab”, word2 = “ab” Output: 3 Explanation: Choose “ab” from word1 and “a” from word2 to make “aba”, which is a palindrome.
Example 3:
Input: word1 = “aa”, word2 = “bb” Output: 0 Explanation: You cannot construct a palindrome from the described method, so return 0.
Constraints: 1 <= word1.length, word2.length <= 1000 word1 and word2 consist of lowercase English letters.word1 and word2 consist of lowercase English letters.
题目要求从两个字符串 word1 和 word2 中分别选出一个非空子序列，并将这两个子序列连接在一起来构造一个最长的回文串，然后返回这个回文串的长度。
在上面那道题的基础上，延伸做法是将 word1 和 word2 直接连接起来，然后在这个连接后的字符串上寻找最长的回文子序列；这道题题目要求的两个子序列都必须是非空的，所以不能只从一个字符串中选出所有字符。
我思路是通过区间动态规划直接从两个字符串中选取字符再判断能否组成一个回文串，然后记录最长的回文长度。
动态规划转移方程推导步骤：
-
如果 word1[i] 和 word2[j] 这两个字符相同则代表这两个字符可以构成回文的两端，形成一个对称的结构。 dp[i][j] = 2 + max(dp[i-1][j-1], dp[0][j-1], dp[i-1][0])。这个状态表示选取这两个字符后还可以从剩下的字符中继续构造回文串，由于之前已经选取了两个字符，且两个子序列都不为空，所以剩余的字符可以是空。
-
如果 word1[i] 和 word2[j] 不同，那么和上一题情况一样需要舍弃一端字符，再选择剩下的部分继续寻找可以构成的回文串。dp[i][j] = max(dp[i-1][j], dp[i][j-1])。这里要确保至少选取一个字符的子序列不为空。如果 i 或 j 的值为 1，那么这个字符必须被选上，否则子序列将为空，这违反了题目的要求。dp[0][i] 和 dp[i][0] 表示的是一个字符串不选取任何字符，另一个字符串选取 i 个字符时所能构成的最长回文串长度，这里直接借用上上一道题的结果，只需要下注意处理字符的下标转换。
-
逐步递推，从 i + j = 2 开始计算，直到 i + j = size1 + size2，最终得到的 dp[size1] [size2] 就是题目要求的最长回文串的长度。
