DP问题求解（三）回文字符串问题
所谓回文字符串，Palindromic Substring，指正序和倒序相同的字符串，如aba=>aba
经典的回文字符串问题
详细题目参考leetcode 5. Longest Palindromic Substring，找出一个字符串中最长的回文子串，如"babad"返回"bab"。
这道很经典的题目，可以用DP来求解，状态方程如下：
status(i,j)=(i+1 > j-1 || status(i+1,j-1) )&& (s[i] == s[j])
其中status(i,j)代表s[i]....s[j]是否是回文字符串，显然，status(i,j)是回文字符，当且仅当status(i+1,j-1)是回文字符并且s[i]==s[j]。
注意考虑为什么要添加i+1 > j-1的判断，因为当j = i + 1的时候，字符子串中只有两个字符，所以只需要对s[i]是否等于s[j]进行判断即可。
状态方程一写出来，整个题目就迎刃而解了。参考代码如下：
string longestPalindrome(string s) {
int len = (int)s.size();
bool status[len][len];
memset(status,false,sizeof(status));
for(int i = 0;i<len;i++){
status[i][i]=true;
}
int maxLen = 1;
int left = 0;
//在这里一定要注意更新status的顺序，不然结果不正确
for(int i = len-2;i>=0;i--){
for(int j = i+1;j<len;j++){
status[i][j] = ((i+1 > j-1) || status[i+1][j-1]) && (s[i] == s[j]);
if(status[i][j] && (j-i+1)>maxLen){
maxLen = j-i+1;
left = i;
}
}
}
return s.substr(left,maxLen);
}
回文字符串分割
详细题目参考leetcode 132. Palindrome Partitioning II，给定一个字符串，在保证分割的子串全都为回文字符串的基础上，返回最少的切割次数。
这道题还有一个初级版本，是返回所有可能的分割方式，原题参考leetcode 131. Palindrome Partitioning，这道题用普通的DFS递归思路就可以解决，具体解决办法等我写DFS系列的时候会详细介绍。如果把这道题的求解思路完全套到上面这道题中，肯定会出现超时错误，因为没有进行任何的状态存储。
所以需要想办法存储下来它的中间状态，下面要说的这种解法，虽然在leetcode上时间排名不高，但我认为比较好理解。
首先为了避免重复对字符子串是否是回文的进行判断，可以按照上一道题中的套路，用一个二维status数组存储该信息，具体步骤和上面那道题一样，就不重复介绍了。
然后使用一个一维数组dp[i]表示子串s.substr(0,i)能构成回文子字符串组合的最少切割次数，这样假设存在k(k < i)，有status[k][i]== true，那么这时候dp[i]可以写成dp[i] = dp[k-1]+1，这样的话遍历所有的k小于i，找到最小的dp[i]值，最后dp[len-1]即为所求，具体代码示例如下：
int status[1500][1500];//如果s过长，在函数内会报错
int minCut(string s) {
int len = (int)s.size();
int dp[len];
dp[0]= 0;
memset(status,false,sizeof(status));
for(int i = 0;i<len;i++){
status[i][i] = true;
}
for(int i = len-2;i>=0;i--){
for(int j = i+1;j<len;j++){
status[i][j] = (i+1 > j-1 || status[i+1][j-1]) && (s[i] == s[j]);
}
}
for(int i = 1;i<len;i++){
int tmp = -1;
for(int j = 0;j<=i;j++){
if(status[j][i]){
if(j == 0){
tmp = 0;
break;
}
if(tmp == -1 || dp[j-1]+1 < tmp){
tmp = dp[j-1]+1;
}
}
}
dp[i] = tmp;
}
return dp[len-1];
}
最长的回文子序列（Subsequence）
这里要说明一下这道题和第一道最长回文子字符串的区别，即 longest palindrome Substring 和 longest palindrome Subsequence，Substring代表子字符串，所选的字符串应该是连续的，而Subsequence子序列则不要求连续，比如"abcdef"中，Subsequence可以为"abdf"，而Substring的下标必须连续。
详细题目参考leetcode 516. Longest Palindromic Subsequence，从给定字符串中找出最长的回文子序列的长度，如输入"bbbab"，输出4（"bbbb"）。
因为没法列举出所有的回文子序列，所以可以考虑用一个二维数组保存最长回文子序列的信息，比如status(i,j)代表s[i]...s[j]之间的最长回文子序列的长度，这样可以写出状态方程：
status(i,j) = max(status(i,j-1),status(i+1,j))
status(i,j) = max(status(i,j),stauts(i+1,j-1)) s[i] == s[j]
最后返回status(0,len-1)即为所求。
参考代码如下：
int longestPalindromeSubseq(string s) {
int len = (int)s.size();
int status[len][len];
memset(status,0,sizeof(status));
for(int i = 0;i<len;i++){
for(int j = i;j<len;j++){
status[i][j] = 1;
}
}
for(int i = len-2;i>=0;i--){
for(int j = i+1;j<len;j++){
status[i][j] = max(status[i+1][j],status[i][j-1]);
if(s[i] == s[j]){
status[i][j] = max(status[i+1][j-1]+2,status[i][j]);
}
}
}
return status[0][len-1];
}
复杂的计算回文子序列个数问题
同样和上面那道题一样是Subsequence问题
详细题目参考leetcode 730. Count Different Palindromic Subsequences，从给定字符串中招待所有不重复回文子序列的个数，由于结果会很大，最终结果去10^9+7的模。如输入"bccb"，返回6。
很显然暴力解肯定会出现超时错误，那应该如何使用dp来保存状态，使用status(i,j)表示s(i)...s(j)之间的回文子序列的个数，那么状态转移方程分为以下几种情况：
-
当s(i) != s(j)时，
此时，status(i,j) = status(i+1,j)+status)i,j-1)-status(i+1,j-1)
-
当s(i) == s(j)时，
又分为以下几种情况：
》当s(i+1)....s(j-1)之间没有和s(i)相同的元素，则
status(i,j)=status(i+1,j-1)*2+2
其中的2增加的是s(i),s(j)两个组成的回文子序列
》当s(i+1)...s(j-1)之间有且只有一个和s(i)相同的元素，则
status(i,j)=status(i+1,j-1)*2+1
其中的1增加的是s(i)s(j)两个组成的回文子序列，而单独的s(i)已经计算过了所以没必要再加了
》当s(i+1)...s(j-1)中有多个和s(i)相同的元素，则
status(i,j)=status(i+1,j-1)*2-status(low+1,high-1)
其中low,high分别代表从左数第一个和s(i)相同的元素，high代表从右数第一个和s(j)相同的元素。减掉的中间部分是重复计算的s(i)s(low+1)...s(high-1)s(j)和s(low)s(low+1)...s(high-1)s(high)
最后需要说明的是，由于结果很可能出现溢出的情况，所以在上面每一步操作中都应该对status(i,j)进行取模操作，而不应该等到最后。又因为在运算中涉及到减操作，很可能得到负值导致结果不正确，所以在status(i,j)为负时应加上模使其变为正，详细代码如下：
int status[1000][1000];
int countPalindromicSubsequences(string S) {
int len = (int)S.size();
int mod = 1000000007;
memset(status,0,sizeof(status));
for(int i = 0;i<len;i++){
status[i][i] = 1;
}
for(int i = len-2;i>=0;i--){
for(int j = i+1;j<len;j++){
if(S[i] != S[j]){
status[i][j] = (status[i][j-1] + status[i+1][j]-status[i+1][j-1])%mod;
}
else{
int low = i+1;
int high = j-1;
while(low <= high && S[low] != S[i]){
low++;
}
while(low <= high && S[high] != S[j]){
high--;
}
if(low > high){
status[i][j] = (2*status[i+1][j-1]+2)%mod;
}
else if(low == high){
status[i][j] = (2*status[i+1][j-1]+1)%mod;
}
else{
status[i][j] = (2*status[i+1][j-1] - status[low+1][high-1])%mod;
}
}
status[i][j] = status[i][j]<0?(status[i][j]+mod)%mod:status[i][j];
}
}
return status[0][len-1];
}
