插入回文串——典型的动态规划区间模型
题目：给定一个长度为n（n <= 1000）的字符串A，求插入最少多少个字符使得它变成一个回文串。
之前我做的DP的问题，大多都是二维的或者一维的，今天就讲下这道典型的一维区间模型。
附上之前写过的二维一维DP模型：
过河问题
最长递增子序列
最长回文子序列
过河卒
问题分析：
一开始看到这个题目的时候，最先让我想到的是之前写过的一道题目最长回文子序列（其实是可以用那道题的二维DP思路解这道题，后面会补充说明，但我先讲解下区间模型）
也许你并不知道如何通过插入最少的字符来使原序列变成一个回文序列，这时候我门不妨换个角度思考下（这也是在做题遇到没思路时的一个小技巧），你肯定知道如何增添字符让一个回文串依旧是回文串，或者让一个回文串不再是回文串。
在这之前，我们先要了解回文序列的特征，当一个序列是回文序列时，如果这个时候我们一定要对其进行增添的操作时，当且仅当在序列的正中间添加一个或者在两边对称添加相同的字符时它还是回文序列，其他的情况（不对称添加或者单个添加）都会使这个回文序列失去回文序列。
也许你会问，这个和题目有什么关系呢？别急，待我慢慢叙说。
我们知道DP的本质是将大问题化为一个个的小问题去解决，那么区间模型就是把大区间逐渐化为小区间去解决，由于回文串的特征，故这个区间是对称缩小的，就是从两边逐渐缩小到中间，而不是单一方向的缩小，如从左缩到右或者从右缩到左（这句话的意思就是有些区间模型是单方向缩小的咯）。
嗯，还是以例子来说明吧。
abc,bad
这个序列要如何修改呢？
假设s[i]表示第i个字符。（从1开始计数）
长度并不长，第一眼看上去也许你会尝试多种可能的情况，对比后得出答案，但我现在带你用DP来解下这道题目
刚刚我们说过这道题要从两边向中间缩，
也许你不知道s[1]到s[7]这串序列的解法，但你不妨先判断下s[1]和s[7]它们各自的值是否相等，如果相等，不就符合我们刚刚所说的回文序列的特征吗？左右刚好对称
如果不相等，因为我们的目标是要让它变成回文，故我们要进行增添操作，刚刚我们又讲过
当且仅当在序列的正中间添加一个或者在两边对称添加相同的字符时它还是回文序列
故我们有两个选择，一个是
在s[1]的左边添加一个值，使它与s[7]一样，
或者在s[7]的右边添加一个值，使它与s[1]一样
选那种呢？当然是选添加最少的那种啦？
也许你会问，这两种情况不是都添加一个值吗？为什么会有多少的问题。
嗯，小朋友，你再思考下，现在我们是不是值判断了最左和最右是否构成了回文的结果啊，中间还有s[2]到s[6]我么没有判断呢~
可以先暂停思考一下，自己设计DP状态转移方程，下面给答案：
dp[i][j] = min( dp[i+1][j]+1, dp[i][j-1]+1 )
代码分析：
#include <bits/stdc++.h>
using namespace std;
char s[1002];
int dp[501][1001];
int palindrome( int i, int j )
{
if ( i>=j )
return 0;
if ( s[i] != s[j] )
dp[i][j] = min( palindrome(i+1,j)+1, palindrome(i,j-1)+1 );
else
dp[i][j] = palindrome(i+1,j-1);
return dp[i][j];
}
int main()
{
scanf ( "%s", s+1 );
int len = strlen(s+1);
cout << palindrome(1,len) << endl;
}
其实上面的代码只能通过一半的测试点，剩下一半的测试点会因为超时而不通过，我在之前的博客有分析递归超时的原因以及解决方法和优化方案，这里就不赘述了，没看过的朋友可以先看看
递归超时怎么办？递归与递推的区别？递归的优化之道
对的，上面有太多重复计算的过程了，可以用记忆化减少计算次数，代码如下：
#include <bits/stdc++.h>
using namespace std;
char s[1002];
int dp[600][1001];
int palindrome( int i, int j )
{
if ( i>=j )
return 0;
if ( dp[i][j] >= 0 )
return dp[i][j];
if ( s[i] != s[j] )
dp[i][j] = min( palindrome(i+1,j)+1, palindrome(i,j-1)+1 );
else
dp[i][j] = palindrome(i+1,j-1);
return dp[i][j];
}
int main()
{
memset(dp,-1,sizeof(dp));
scanf ( "%s", s+1 );
int len = strlen(s+1);
cout << palindrome(1,len) << endl;
}
另一种记忆化写法：
#include <bits/stdc++.h>
using namespace std;
char s[1100];
int dp[1100][1100];
int mark[1100][1100];
int palindrome( int i, int j )
{
if ( i>=j )
return 0;
if ( mark[i][j] == 1 )
return dp[i][j];
if ( s[i] != s[j] )
{
dp[i][j] = min( palindrome(i+1,j)+1, palindrome(i,j-1)+1 );
mark[i][j] = 1;
}
else
{
dp[i][j] = palindrome(i+1,j-1);
mark[i][j] = 1;
}
return dp[i][j];
}
int main()
{
scanf ( "%s", s+1 );
int len = strlen(s+1);
cout << palindrome(1,len) << endl;
}
方案二：二维DP
在开头的时候就点了一下，可以用传统的二维DP来做，整体思路就是先求出改字符串的最大回文子序列，保证这个结构不变，然后对那些不对称的零散的字符进行对称添加就好了，关于如何求最大回文子序列，之前有专门写文章说过，证明过程也很详细，这里就不赘述了，如果还是不懂，可以看下这篇文章。代码也在下面，同样AC了。
最长回文子序列
#include <bits/stdc++.h>
using namespace std;
char s[1001];
char reverse_s[1001];
int dp[1001][1001];
int main()
{
scanf ( "%s", s+1 );
int len = strlen(s+1);
int i, j;
for ( i=1; i<=len; i++ )
{
reverse_s[i] = s[len-i+1];
}
for ( i=1; i<=len; i++ )
for ( j=1; j<=len; j++ )
if ( reverse_s[i] == s[j] )
dp[i][j] = dp[i-1][j-1]+1;
else
dp[i][j] = max( dp[i-1][j], dp[i][j-1] );
cout << len-dp[len][len] << endl;
return 0;
}
写在后面：
为了确保大家能够看懂这篇文章，我尽量每字每句都详细讲解，给出证明和解释，真心希望你能够在阅读此篇文章后从中多多少少有所收获。因此每篇文章我都投入了大量的时间和精力，去举例，去说明，去分析，如果你觉得这篇文章写的还不错，点赞、关注和收藏一键三连就是对我最大的鼓励啦，我以后也会写更多更高质量的文章！也欢迎一起讨论指出文章可能存在的逻辑问题~
