求長度小於 1000 的字元串的最長子序列的思路應該是怎樣的？

題面大致意思是給定一個字元串(長度小於1000)，例如：cabbeaf，刪除c,e,f後可得到最長的迴文子序列abba，長度為4。現在輸入一個字元串，求刪除部分字母后能得到的最長迴文子序列長度。

乍一看覺得和以前做過的動態規劃題很像，但是一下子沒想出方案，然後臨時YY了一個演算法：

輸入字元串為s1，reverse之後得到s2，然後求s1與s2的lcs長度，竟然也過了樣例然後自己測了幾組也對了。

想問這個題的正確演算法應該是怎樣？我這個演算法對不對，如果對該怎麼證明是正確的？

PS：忽然想起來剛剛擼代碼的時候把lcs擼成lcm了。。。

---

你的思路其實沒錯，把字元串逆序以後，然後和原字元串串進最長公共子序列是可以求最長迴文串的，所以其實就是求LCS。

這道題的難度沒有Uva11404大，這道題要求字典序最小：UVa Online Judge

---

這個題的題目不太理解，他說cabebaf的最長迴文子串是abba。。難道不是abeba嗎？

---

定義OPT(i, j) 為字元串能夠得到的最長迴文串長度。則OPT(i, i) = 1（只有一個字元）, OPT(i, i-1) = 0（空字元串）。

的情況下：

• 如果, OPT(i, j) = 2 + OPT(i+1, j-1) //保留首尾字元
• 否則，OPT(i, j) = max{OPT(i+1, j), OPT(i, j-1)} //任意保留一個選最大

偽代碼：

// Initialize OPT[i, i] = 1 for i = 1...n
// Initialize OPT[i, i-1] = 0 for i = 2,...,n
for j = 2,...,n
for i = j-1,...,1
if si == sj
OPT[i, j] = 2 + OPT[i+1, j-1]
else
OPT[i, j] = max{OPT[i+1, j], OPT[i, j-1]}


*提取最長迴文串：

i = 1, j = n
while i &< j if si == sj //Case 1 i++; j-- else if OPT[i, j] == OPT[i+1, j] //Case 2 mark si to be deleted; i++ else //Case 3 mark sj to be deleted. j--

---

做法是對的，證明也是顯然的？最長迴文子串顯然是S和其reverse SR的一個公共子串，而LCS(S,SR)也顯然是一個最長迴文子串，這意味著兩者的長度必定相等。

不過我第一次做這道題的時候並沒有能夠直接想到這個解法，而是在一個更暴力的方法上優化得到的，雖然最後的本質一樣：

（為了方便討論，暫假設迴文子串是偶數長度的，奇數長度不影響結論。）

一個naive的做法是，我們可以枚舉出迴文子串中點在S的位置，然後把S拆分成兩個部分，其中一個部分reverse一下，和後一個部分求LCS，得到的結果乘2就是答案。

然後可以比較容易的發現，枚舉位置再拆分計算LCS是不必要的，可以先求出LCS(S, SR)，然後再枚舉拆分點就可以了，這樣子的做法已經很接近題主的方法了。但是還多了一步枚舉，進一步思考，為什麼我們要枚舉拆分點呢？我們其實並不需要知道拆分點的具體位置，因為我們在枚舉拆分點以後將結果＊2，而這個結果一定是整個串的LCS，因此直接算LCS(S,SR)就可以得到答案了。

---

這題題目描述坑爹 哪裡是子串 分明是子序列 不過也怪自己沒看清題 弄成最長迴文子串 常見解法就是求它本身和逆序串的最長公共子序列

---

為什麼全在用逆序後求LCS？不是很奇怪嗎？

直接區間dp啊！

f[i][j]表示，在下標[i,j]的子串中，最長迴文子序列是多長
if(input[i]==input[j])
f[i][j]=f[i+1][j-1]+(i==j?1:2);
else f[i][j]=max(f[i+1][j],f[i][j-1]);


這麼理解這個方程：

如果input[i]和input[j]一樣，那這2個字母應該被取來構成最長迴文子序列

如果不一樣，那考慮刪去i或j的子串中的最長迴文子序列。

枚舉的時候，先從長度為1的子串開始枚舉，之後是長度為2的，一直到長度為n的。

具體代碼如下：

#include &
#include &
#include &
using namespace std;

char str[1005];
int f[1005][1005];

int main(){
scanf("%s",str);
int len=strlen(str);
//感謝下面@侯岩的提醒，穩妥起見，長度為1的應該特殊處理。
for(int i=0;i&

---

這種方法好像有點太技巧了，並不容易想到。直接dp好像更簡單一點。

dp[k][i] = max(dp[k-1][i], dp[k-1][i+1]);

if (str[i-1] == str[i+k-1-1])

dp[k][i] = max(dp[k][i], 2+dp[k-2][i+1]);

k從2開始，dp[1] 初始化為全1。

---

昨晚我也考了這道題。然後想了個遞歸的方法。

#include &

#include &

using std::string;

int LoopString(const string str, size_t start, size_t end) {

if (start &> end || end &>= str.size()) {

return 0;

}

else if (start == end) {

return 1;

}

int len = 0;

if (str[start] == str[end]) {

len = LoopString(str, start + 1, end - 1) +　２;

} else {

len = LoopString(str, start + 1, end);

int temp = LoopString(str, start, end -1);

if (temo &> len) {

len = temp;

}

}

return len;

}

int main() {

string str;

std::cin&>&>str;

int len = LoopString(str, 0, str.size() - 1);

std::cout&<&

return 0;

}

當時自己是這樣想的：

一個字元串的最長迴文，有三種情況：

1.兩端相等，那麼就會是去掉這兩端的兩個字元的子串的最大迴文字元串長度＋２；

２.兩端不等：代表有可能至少一端不包含在最長迴文字元串中，那麼就分別減去，要麼在減去前面字元的子串中找，要麼在減去後面的子串中找。

這樣遞歸就寫出來了。

稍微吐槽一下，我全屏寫代碼的時候，測試完，關掉全屏時，發現自己代碼都沒了T_T，嚇到我按到了後退鍵（我滑鼠旁邊有個後退的快捷鍵），還好進去之後還剩下一部分代碼。冷汗都嚇出來了。。。。T_T

我的函數名其實是亂來的，不知道迴文怎麼拼T_T。

---

卧槽，我還是太嫩，怎麼就沒想到LCS

---

我用的遞歸。感覺哪裡不對。

開頭i結尾j

首先移動i，j不動，找有沒有相同的。有遞歸重置i j 最後++

沒有就移動j一下，繼續移動i，若有，繼續遞歸重置i j 最後++

若i大於等於j返回0

---

題主跟我思路一模一樣…騰訊會不會認為咱倆作弊…

---

int subPalin(const string str) {
size_t size = str.length();
int res = 1;
vector&&> dpTmp(size, vector&(size, 0));
for (int i = 0; i &< size; i++) for (int j = i; j &>= 0; j--) {
if (i == j) dpTmp[i][j] = 1;
else if (i == j + 1) dpTmp[i][j] = (str[i] == str[j] ? 2 : 1);
else {
int tmpMax = dpTmp[i-1][j+1] + (str[i] == str[j] ? 2 : 0);
dpTmp[i][j] = max(tmpMax, max(dpTmp[i - 1][j], dpTmp[i][j + 1]));
}
res = max(res, dpTmp[i][j]);
}
return res;
}


我也不知對不對，請大神指導。

---

我在leetcode做過的這個，剛才翻了一下竟然沒找到，，，

LCS（X,X1） = LPS（X）當時提示里也是這麼說的

這樣動態規劃就簡單了，一個正的一個反的，看他們開頭字母一不一樣，一樣 返回 1 +刪掉最開頭兩個字元 ， 不一樣隨便刪一個選最大的

半夜無聊，代碼在這裡，我絕對在leetcode上做過，為什麼找不到呢

def sovle(s):
def iter(s,reverse_s):
if not s or not reverse_s:
return 0
if s[0] == reverse_s[0]:
return 1 + iter(s[1:],reverse_s[1:])
else:
return max(iter(s,reverse_s[1:]),iter(s[1:],reverse_s))
return iter(s,s[::-1])

print(sovle("cabbeaf"))


---

動態規劃吧，感覺和求迴文子序列數量的差不多

這裡有一篇動態規劃求一個序列的最長迴文子序列（Longest Palindromic Substring ）

---

最長迴文子序列不是子串。經典的區間DP啊，一開始按照馬拉車寫了好一陣子發現樣例都過不去(っ╥╯﹏╰╥c)

---

推薦閱讀：