【每日一题】3月26日题目精讲 区间dp、最长回文子序列

名称：合并回文子串

来源：美团2017年CodeM大赛-初赛A轮

戳我进入往期每日一题汇总贴~

------------------------------------以下是和本题还有点关系的相关知识讲解-----------------------------
首先，我们来复习一下区间dp的经典问题：最长回文子序列（如果你没有学过也不不要紧，我会努力写得容易看懂一些）
——给你一个字符串，求一个最长的回文子序列（可以不连续）。
一般情况下，动态规划的解题步骤是：
第一步：根据原问题和子问题来确定状态（我的dp数组要表示什么东西）
第二步：根据状态确定状态转移方程（递推式，怎样求解dp数组）
第三步：确定要不要优化和编程实现方式
（其实你可以这样理解——第一步是确定“我是谁，我在哪”，第二步是确定“我从哪里来”或者“我到哪里去”，第三步是确定“我怎么去”。）
对于本题来说：
原问题是：给定字符串 的最长回文子序列
子问题其实是把原问题进行分解，缩小范围，往往一个问题的子问题会有很多种表示方法，比如说： 前 个字符的最长回文子序列， 后 个字符的最长回文子序列等等等，这个时候要结合题目来看——我们知道回文串是个左右对称的结构，所以一个回文串的增加长度是通过左右两边各加一个相同字母来实现的，所以，我们倾向于把子问题描述成：“字符串 的第 个字符到第 个字符的最长回文子序列长度”，那么我们就用dp数组来表示它—— 为字符串 的第 个字符到第 个字符的最长回文子序列长度。
状态确定之后我们需要来考虑这个状态是怎么来的（怎么来和到哪里去考虑一个就好，过程是对称的）。考虑这个状态是如何得来的时候，只需要考虑最后一步是怎么走的，前面的步骤的包含着之前的状态里面了。
具体到这个题Dp[i][j] 有两种情况：
s[i] == s[j]：这个时候可以把s[i]和s[j]分别加到原来0的回文子序列的两端，也就是 i+1 到 j-1 这个区间的字符构成的最长回文子序列的两端，此时 ;
s[i] != s[j]：那么在 到 这个区间的最长回文子序列中第 个字符和第 个字符一定不能同时存在，所以是可以扔掉他俩中的某一个的（并不是任意一个），此时 。
其他的情况都是这两种情况的子情况了所以转移方程就出来啦！

在这个问题看懂之后，我们再来讨论一个最长回文子串问题——给你一个字符串，求一个最长的回文子串（连续）。这个问题有非常优秀的O（n）的manacher算法，但是由于和本题没有关系，我在这里只给大家介绍 的dp（你可以作为一种解决问题的思路去学习它，同时它也可以加深你对区间dp的认识）。
我们可以像上个题一样尝试用 dp[i][j] 为字符串 的第 个字符到第 个字符的最长回文子串长度，这时候我们发现，没有办法转移——因为我们不知道第 个字符和第 个字符的选择状况，所以无法转移（更准确的说，当 dp[i][j]!=j-i+1，即第 个和第 个里面至少有一个没选的时候，区间以外的字符我们就不知道是否能选了。）那怎么办呢？我们可以强行规定 中第 个字符和第 个字符都必须选，换句话说 其实是选完了整个 到 的区间的，也就是说，dp[i][j] ==j-i+1时，这个区间是个回文串，否则就不是，。
这样子的话， 存的其实不是回文子串的长度，而是 到 这个区间是不是回文子串（1表示是，0表示不是）。
只有满足 且 dp[i+1][j-1]==1， 才能等于1，否则都是0。即如果一个串是回文串，往他两边各加一个相同的字母也是回文串，否则就不是回文串了。

-----------------------------------以下是本题解法的分界线-------------------------------------------------------
那么我们终于可以回到“合并回文子串”这个题，如果我们用表示前一个串（a串）的第 个字符到第 个字符后一个串（b串）的第 个字符到第 个字符能否组成一个回文串的话，有四种可能，四种当中任意一种为真f[i][j][k][l]就是真。
往 到 和 到 构成的串的两端加上 和 两个字符：

往 到 和 到 构成的串的两端加上 和 两个字符：

往 到 和 到 构成的串的两端加上 和 两个字符：

往 到 和 到 构成的串的两端加上 和 两个字符：

问题解决，其实我们可以看到，这个朴素的最长回文子串问题并没有实质上的区别，只是首尾两端加字母的选择从原来的一种变成了2*2种。
若是你没有写过区间dp的话，我提醒一点：区间dp要从短区间扩展到长区间，所以如果你不是使用记忆化搜索的话，就需要按区间长短来枚举而不是直接枚举首末端点！
一个小问题可能出现在边界上：的真假性显而易见的等于 的真假性，但是转移过程中有可能找 a/b 串中有一个串一个字符都没有选的情况去转移，这个处理非常简单：只要两个串选中的字符个数等于1，直接f值等于1就好（果选中的字符个数小于1，那已经是非法状态了）
代码可戳我查看~

活动奖励：

在牛客博客中写出题解，并回复地址

审核通过可获得10-50牛币（依据题目难度和题解的内容而定）