DP問題求解（三）回文字符串問題
所謂回文字符串，Palindromic Substring肮塞，指正序和倒序相同的字符串襟齿，如aba=>aba
經(jīng)典的回文字符串問題
詳細題目參考leetcode 5. Longest Palindromic Substring，找出一個字符串中最長的回文子串枕赵，如"babad"返回"bab"猜欺。
這道很經(jīng)典的題目，可以用DP來求解拷窜，狀態(tài)方程如下：
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]進行判斷即可挽鞠。
狀態(tài)方程一寫出來疚颊，整個題目就迎刃而解了。參考代碼如下：
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材义，給定一個字符串，在保證分割的子串全都為回文字符串的基礎上嫁赏，返回最少的切割次數(shù)其掂。
這道題還有一個初級版本，是返回所有可能的分割方式潦蝇，原題參考leetcode 131. Palindrome Partitioning款熬，這道題用普通的DFS遞歸思路就可以解決，具體解決辦法等我寫DFS系列的時候會詳細介紹攘乒。如果把這道題的求解思路完全套到上面這道題中贤牛，肯定會出現(xiàn)超時錯誤，因為沒有進行任何的狀態(tài)存儲则酝。
所以需要想辦法存儲下來它的中間狀態(tài)殉簸，下面要說的這種解法，雖然在leetcode上時間排名不高，但我認為比較好理解般卑。
首先為了避免重復對字符子串是否是回文的進行判斷武鲁，可以按照上一道題中的套路，用一個二維status數(shù)組存儲該信息蝠检，具體步驟和上面那道題一樣洞坑，就不重復介紹了。
然后使用一個一維數(shù)組dp[i]表示子串s.substr(0,i)能構成回文子字符串組合的最少切割次數(shù)蝇率，這樣假設存在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過長监氢，在函數(shù)內(nèi)會報錯
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）
這里要說明一下這道題和第一道最長回文子字符串的區(qū)別，即 longest palindrome Substring 和 longest palindrome Subsequence藤违，Substring代表子字符串浪腐，所選的字符串應該是連續(xù)的，而Subsequence子序列則不要求連續(xù)顿乒，比如"abcdef"中议街，Subsequence可以為"abdf"，而Substring的下標必須連續(xù)璧榄。
詳細題目參考leetcode 516. Longest Palindromic Subsequence特漩，從給定字符串中找出最長的回文子序列的長度，如輸入"bbbab"骨杂，輸出4（"bbbb"）涂身。
因為沒法列舉出所有的回文子序列，所以可以考慮用一個二維數(shù)組保存最長回文子序列的信息搓蚪，比如status(i,j)代表s[i]...s[j]之間的最長回文子序列的長度蛤售，這樣可以寫出狀態(tài)方程：
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];
}
復雜的計算回文子序列個數(shù)問題
同樣和上面那道題一樣是Subsequence問題
詳細題目參考leetcode 730. Count Different Palindromic Subsequences妒潭，從給定字符串中招待所有不重復回文子序列的個數(shù)悴能，由于結果會很大，最終結果去10^9+7的模杜耙。如輸入"bccb"搜骡，返回6。
很顯然暴力解肯定會出現(xiàn)超時錯誤佑女，那應該如何使用dp來保存狀態(tài)记靡，使用status(i,j)表示s(i)...s(j)之間的回文子序列的個數(shù)谈竿，那么狀態(tài)轉移方程分為以下幾種情況：
-
當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)已經(jīng)計算過了所以沒必要再加了
》當s(i+1)...s(j-1)中有多個和s(i)相同的元素，則
status(i,j)=status(i+1,j-1)*2-status(low+1,high-1)
其中l(wèi)ow,high分別代表從左數(shù)第一個和s(i)相同的元素啼止，high代表從右數(shù)第一個和s(j)相同的元素道逗。減掉的中間部分是重復計算的s(i)s(low+1)...s(high-1)s(j)和s(low)s(low+1)...s(high-1)s(high)
最后需要說明的是，由于結果很可能出現(xiàn)溢出的情況献烦，所以在上面每一步操作中都應該對status(i,j)進行取模操作滓窍，而不應該等到最后。又因為在運算中涉及到減操作巩那，很可能得到負值導致結果不正確吏夯，所以在status(i,j)為負時應加上模使其變?yōu)檎敿毚a如下：
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];
}
