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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
