POJ 1159 Palindrome DP

제목: 문자열을 지정합니다. 최소한 몇 글자를 삽입해야만 문자열을 회문열로 만들 수 있습니다.문제풀이: 세 가지 방법을 총결하였는데 구체적으로는 다음과 같다.방법1:s1은 원 문자열이고 s2는 s1이 오른쪽에서 왼쪽으로 복사합니다.dp[i][j]는 s1[i]와 s2[j] 왼쪽의 문자열을 완전히 동일하게 하고 최소한 삽입해야 하는 문자 개수를 나타낸다.1. s1 [i]를 한다!!=s2[j]시 이미 알고 있는 것으로 가정하면substr1:··········s1[i-1]substr2:·······s2[j]substr1===substr2는 현재 dp[i][j]를 요구하고 있으며, 반드시 s2[j]의 오른쪽에 s1[i]와 같은 문자를 추가해야 한다. 즉,substr1:·········s1[i],s1]substr2:········j·s2,s2,s1s1'[i] 그럼 dp[i] [j] = dp [i-1] [j] + 1 동리: dp [i] [j] = dp [i] [j-1] + 1;그러면 dp[i][j]=min(dp[i-1][j]+1, dp[i][j-1]+1);2. s1[i]=s2[j]일 때 이미 알고 있는 경우:substr1:········s1[i-1]substr2:········s2[j-1]substr1==substr2dp[i]=dp[i][j-1][j-1] 주의:s2는 s1이 오른쪽에서 왼쪽으로 복제한 것이기 때문에 대칭성에 따라 대칭적이다.답은 dp[len][len]/2.(나는 dp[len/2][len/2]만 구해 보았지만, 어떤 세부 사항은 고려하지 못하고 자꾸 wrong, 포기했다. 알고 있는 번거로움은 회답한다.)2. 초기화 주의, dp [i] [0] = dp [0] [i] = i.이치는 매우 간단하다. 만약에 s1의 i 문자가 s2의 0 문자의 왼쪽과 완전히 같다면 s2의 왼쪽에 s1[1], s1[2]···s1[i]를 추가해야 한다. 

#include <iostream>
using namespace std;

#define N 5005
short dp[N][N];
char s1[N], s2[N];

int min ( int a, int b )
{
	return a < b ? a : b;
}

int main()
{
	int len, i, j;
	while ( scanf("%d",&len) != EOF )
	{
		scanf("%s",s1+1);
		i = 1; j = len;
		while ( i <= len && j >= 1  )
		{
			s2[i] = s1[j];
			i++; j--;
		}
		
		for ( i = 0; i <= len; i++ )
			dp[i][0] = dp[0][i] = i;
		
		for ( i = 1; i <= len; i++ )
		{
			for ( j = 1; j <= len; j++ )
			{
				if ( s1[i] == s2[j] )
					dp[i][j] = dp[i-1][j-1];
				else		
					dp[i][j] = min (  dp[i-1][j] + 1, dp[i][j-1] + 1 );
			}
		}
		printf("%d
", dp[len][len] / 2 );
	}
	return 0;
}

방법2:
최대 공통 서열을 구합니다.
s1, s2를 알고 있습니다. 같은 s2는 s1이 오른쪽에서 왼쪽으로 복사한 것입니다.
s1[1], s1[2], ·······s1[i] ····················
s2[1], s2[2], ·······················s2[j],····
s1==s2를 위해 우리는 s1을 만날 때마다 [i]!=s2[j], 모두 s1에 s2'[j]를 추가하고 s2에 문자s1'[i]를 추가하면 다음과 같이 됩니다.
s1[1], s1[2], ·······s1 [ i ] ···············s2'[ j ]·····
s2[1], s2[2], ·······s1'[ i ]················s2 [ j ]·····
최종적으로 반드시 s1==s2, 즉 회문열을 얻을 수 있다.이때 s1에 추가된 문자 개수는 s1 [i] 와 꼭 같습니다!s2[j]의 대수.즉, 문자 개수 = 렌 - 공통 서열 길이를 추가하기 때문에 가장 긴 공통 서열만 요구할 수 있습니다.

#include <iostream>
using namespace std;

#define N 5005
short dp[N][N];
char s1[N], s2[N];

int max ( int a, int b )
{
	return a > b ? a : b;
}

int main()
{
	int len, i, j;
	//freopen("a.txt","r",stdin);
	while ( scanf("%d",&len) != EOF )
	{
		scanf("%s",s1+1);
		i = 1; j = len;
		while ( i <= len && j >= 1  )
		{
			s2[i] = s1[j];
			i++; j--;
		}
		
		for ( i = 1; i <= len; i++ )
			dp[i][0] = dp[0][i] = 0;
		
		for ( i = 1; i <= len; i++ )
		{
			for ( j = 1; j <= len; j++ )
			{
				if ( s1[i] == s2[j] )
					dp[i][j] = dp[i-1][j-1] + 1;
				else
					dp[i][j] = max ( dp[i-1][j], dp[i][j-1] );
			}
		}
	
		if ( dp[len][len] == 0 ) dp[len][len] = 1;
		printf("%d
", len - dp[len][len] );
	}
	return 0;
}

방법3: s[1]를 설정한다.s[n]는 문자열 1에서 n위, i는 왼쪽 커서, j는 오른쪽 커서를 나타낸다. 그러면 i는len에서 감소하고 j는 i+1에서 증가한다.이렇게 하는 효과는 맨 오른쪽 부분을 회문열로 바꾸기 시작한 다음에 회문열이 점점 왼쪽으로 커지는 것이다.dp[i][j]는 i와 j 사이에 최소한 몇 개의 문자를 삽입해야만 국부적인 회문열을 구성할 수 있음을 나타낸다. 처음에 모두 0을 설정했는데 우리가 최종적으로 얻어야 할 값은 dp[1][n]이다.그러면:if(s[i]=s[j])//만약 두 커서가 가리키는 문자가 같으면 가운데로 범위를 축소하여 dp[i][j]=dp[i+1][j-1];elsedp[i][j]=1+min(dp[i+1][j],dp[i][j-1]) 아래 코드는 스크롤 그룹으로 메모리를 최적화시켰다.

#include <iostream>
using namespace std;

#define N 5005
short dp[2][N];
char s[N];

int min ( int a, int b )
{
	return a < b ? a : b;
}

int main()
{
	int len,i,j;
	//freopen("a.txt","r",stdin);
	while ( scanf("%d",&len) != EOF )
	{
		scanf("%s",s+1);
		memset(dp,0,sizeof(dp));
		for ( i = len; i >= 1; i-- )
		{
			for ( j = i+1; j <= len; j++ )
			{
				if ( s[i] == s[j] )
					dp[i%2][j] = dp[(i+1)%2][j-1];
				else
					dp[i%2][j] = min ( dp[i%2][j-1], dp[(i+1)%2][j] ) + 1;
			}
		}
		printf ( "%d
",dp[1][len]);
	}
	return 0;
}