POJ 1159 Palindrome 題解

POJ 1159 Palindrome 題解

本題的題意理解之後，就是求最長回文子序列 longest palindrome subsequence，這裡注意子序列和子串的區別。

有兩種求法，一種是直接求，相當於填矩陣右上對角陣，另一種是轉化為longest common subsequence的求法。

最大難點就是要求內存不能使用二維的。 故此第一種方法是有點難度的，因為需要把二維矩陣的對角線轉化為一維表記錄，對好下標就好了。

第二中方法會稍微容易點，效率都是一樣的O(n*n)。

方法1：

#include 

const int MAX_N = 5001;//超過這個輸入，如果是MAX_N*MAX_N的內存都會超內存
int len;
char chs[MAX_N];
inline int max(int a, int b) { return a > b? a : b; }
int tbl[2][MAX_N];

int longestPalindromeSequence()
{
	for (int i = 0; i < len; i++) tbl[0][i] = 1;
	bool id = false;

	for (int d = 2; d <= len; d++)
	{
		id = !id;
		for (int i = 0, j = i+d-1; j < len; i++, j++)
		{
			if (chs[i] == chs[j] && d == 2) tbl[id][i] = 2;
			else if (chs[i] == chs[j]) tbl[id][i] = tbl[id][i+1] + 2;
			else tbl[id][i] = max(tbl[!id][i], tbl[!id][i+1]);
		}
	}
	return tbl[id][0];
}

int main()
{
	while (~scanf("%d", &len))
	{
		getchar();	//Don't forget the last line's '\n' character.
		gets(chs);
		printf("%d\n", len - longestPalindromeSequence());
	}
	return 0;
}

#include 
#include 
#include 
using namespace std;
const int MAX_N = 5001;//超過這個輸入，如果是MAX_N*MAX_N的內存都會超內存
int len;
char chs[MAX_N];
char revChs[MAX_N];
inline int max(int a, int b) { return a > b? a : b; }
int tbl[2][MAX_N];

int longestCommonSequence()
{
	memset(tbl[0], 0, sizeof(int)*(len+1));
	tbl[1][0] = 0;
	bool id = false;
	for (int i = 0; i < len; i++)
	{
		id = !id;
		for (int j = 0; j < len; j++)
		{
			if (chs[i] == revChs[j]) tbl[id][j+1] = tbl[!id][j] + 1;
			else tbl[id][j+1] = max(tbl[!id][j+1], tbl[id][j]);
		}
	}
	return tbl[id][len];
}

int main()
{
	while (~scanf("%d", &len))
	{
		getchar();	//Don't forget the last line's '\n' character.
		gets(chs);
		strncpy(revChs, chs, len);
		reverse(revChs, revChs+len);
		printf("%d\n", len - longestCommonSequence());
	}
	return 0;
}