CTDL và giải thuật - Giải thuật Qui hoạch động

Một chuỗi s được gọi là đối xứng nếu khi viết ngược s lại thì s vẫn không thay đổi, ví dụ "1221""232" là chuỗi đối xứng, còn"123" không là chuỗi đối xứng.

Cho một chuỗi s, hãy xóa một số ký tự trong s để được một chuỗi đối xứng dài nhất. Nếu có thể tạo được nhiều chuỗi đối xứng cùng độ dài thì đưa ra chuỗi đầu tiên.

Ví dụ:

  • Test mẫu 1:
     
    Input Output
    aabbsca abba

    Với s = "aabbsca" thì longestPalindrome(s) = "abba".
    Giải thích: Chúng ta sẽ xóa các ký tự 'a', 's' và 'c'.
     
  • Test mẫu 2:
     
    Input Output
    123a 1

    Với s = "123a" thì longestPalindrome(s) = "1".

Hướng dẫn bài tập.

Code mẫu:

Ngôn ngữ C++:

#include<iostream>

using namespace std;

int l[1001][1001];
string longestChainSymmetry(string s)
{
    string x = s;
    string y = "";
    for (int i = s.length() - 1; i >= 0; i --) y = y + x[i];
    int m = x.length(), n = y.length();
    x = ' ' + x;
    y = ' ' + y;
	for (int i = 0; i <= m; i++) l[i][0] = 0;
	for (int j = 0; j <= n; j++) l[0][j] = 0;
    for (int i = 1; i <= m; i++) 
	for (int j = 1; j <= n; j++) {
        if (x[i] == y[j]) l[i][j] = l[i-1][j-1] + 1;
        else l[i][j] = max(l[i-1][j], l[i][j-1]);
    } 
    string p = "";
    while (l[m][n] > 0 && m > 0 && n > 0){
    	while (l[m-1][n] == l[m][n]) m --;	 
		while (l[m][n] == l[m][n-1]) n --;	
		p = x[m] + p;
		m --;
		n --; 	
	}
   return p;
}
int main(){
    string s;
    getline(cin, s);
    cout << longestChainSymmetry(s);
    return 0;
}