สมมติว่าเรามีสตริง s เราต้องหาความยาวของลำดับย่อยพาลินโดรมที่ยาวที่สุดในหน่วย s เราสามารถสรุปได้ว่าความยาวสูงสุดของ s คือ 1,000 ดังนั้นหากอินพุตเป็นเหมือน “bbbab” เอาต์พุตจะเป็น 4 ลำดับย่อยของพาลินโดรมที่เป็นไปได้อย่างหนึ่งคือ “bbbb”
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- x :=s แล้วย้อนกลับ x, n :=ขนาดของ s
- ถ้า n เป็น 0 ให้คืนค่า 0
- อัปเดต s โดยเพิ่มช่องว่างก่อน s และอัปเดต x โดยเพิ่มช่องว่างก่อน x
- ret :=0
- สร้างเมทริกซ์หนึ่งขนาด dp (n + 1) x (n + 1)
- สำหรับฉันอยู่ในช่วง 1 ถึง n
- สำหรับ j ในช่วง n ถึง n
- dp[i, j] :=สูงสุดของ dp[i, j – 1], dp[i – 1, j]
- ถ้า x[i] =s[j] แล้ว dp[i, j] :=สูงสุดของ dp[i, j] และ 1 + dp[i – 1, j – 1]
- สำหรับ j ในช่วง n ถึง n
- ส่งคืน dp[n, n]
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int longestPalindromeSubseq(string s) {
string x = s;
reverse(x.begin(), x.end());
int n = s.size();
if(!n) return 0;
s = " " + s;
x = " " + x;
int ret = 0;
vector < vector <int> > dp(n + 1, vector <int>(n + 1));
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n ; j++){
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
if(x[i] == s[j]) {
dp[i][j] = max(dp[i][j], 1 + dp[i - 1][j - 1]);
}
}
}
return dp[n][n];
}
};
main(){
Solution ob;
cout << (ob.longestPalindromeSubseq("bbbab"));
} อินพุต
"bbbab"
ผลลัพธ์
4
