poj1159 Palindrome (dp)

두 가지 방법:
1. 서열 i~j는 회문, 두 가지 전략:
(1)str[i]==str[j]라면 i+1~j-1만 회문하면 됩니다. 이때: dp[i][j]=dp[i+1]j-1;(2) 그렇지 않으면str[j] 뒤에 문자str[i]를 추가하고 i+1~j를 회문으로 하거나
str[i] 이전에 str[j]를 추가하고 i~j-1을 회문으로 합니다. 이때: dp[i][j]=맥스(dp[i+1][j]+1, dp[i][j-1]+1).(이 경우 공간이 넓어 반드시 short를 사용해야 함)
2.str와 ~str의 가장 긴 공통 서열을 구하고, 답은 n-가장 긴 공통 서열의 문자 개수입니다.
dp[i][j]는str와~str의 가장 긴 공통 서열의 문자수입니다.str[i]와~str[j]가 같으면 dp[i]=dp[i-1]j-1]+1;그렇지 않으면 dp[i][j]=MAX(dp[i][j-1], dp[i-1][j]).
방법 1:

#include <iostream>
using namespace std;

#define MIN(a, b) a<b?a:b
#define M 5002

char str[M];
short dp[M][M];

int main()
{
	int n, l, i, j;
	
	memset(dp, 0, sizeof(dp));
    scanf("%d %s", &n, str);
    for(l = 2; l <= n; l++){
		for(i = 0; i+l-1 < n; i++){
			j = i+l-1;
			if(str[i] == str[j])
				dp[i][j] = dp[i+1][j-1];
			else 
				dp[i][j] = MIN(dp[i][j-1]+1, dp[i+1][j]+1);
		}
	}
	printf("%d
", dp[0][n-1]);
	
	return 0;
}

메서드 2: 배열 스크롤

#include <iostream>
using namespace std;

#define MAX(a, b) a>b?a:b
#define M 5005

int a[M], b[M], *tmp, *p = a, *q = b; //    ，        ， i      i-1     ，        ，      
char str[M];

int main()
{
   int n, i, j, k;

   scanf("%d
%s", &n, str+1);
   memset(p, 0, sizeof(p));
   for(i = 1; i <= n; i++){
	   for(j = 1; j <= n; j++){
	       k = n-j+1;
		   if(str[i] == str[k])
		       q[j] = p[j-1]+1;
		   else
			   q[j] = MAX(q[j-1], p[j]);
	   }
	   tmp = q; q = p; p = tmp;
   }
   printf("%d
", n-p[n]);
   return 0;
}