최소한 의 문 자 를 삽입 하여 문자열 을 답장 문자열 로 만 듭 니 다.
2377 단어 알고리즘
문자열 S 를 지정 하면 문자열 의 임의의 위치 에 문 자 를 삽입 하여 답장 문자열 로 바 꿀 수 있 습 니 다.최소 삽입 문자 의 수 를 구하 십시오.
제목:https://vjudge.net/problem/POJ-1159
해법 1:
S 에서 답문 의 가장 긴 하위 서열 L 을 구하 면 결과 ans = length (S) - length (L), 해법 은 다음 과 같다.
1. S 의 역 주 행 S 를 구한다 '
2. S 와 S 의 최 장 공통 서열 L 구하 기
3. ans = length(S) - length(L)
코드 는 다음 과 같 습 니 다:
#include
#include
#include
using namespace std;
const int N = 5001;
int dp[2][N];
int getLSCLength(int len, string s1, string s2) {
memset(dp, 0, sizeof(dp));
int e = 0;
for (int i = 1; i <= len; i++) {
e = 1 - e; // ， ， ，
for (int j = 1; j <= len; j++) {
if (s1[i-1] == s2[j-1]) {
dp[e][j] = dp[1-e][j-1] + 1;
} else {
dp[e][j] = max(dp[1-e][j], dp[e][j-1]);
}
}
}
return dp[e][len];
}
int main() {
int n;
string s;
cin >> n >> s;
string t(s.rbegin(), s.rend());
int lsc = getLSCLength(n, s, t);
cout << s.length() - lsc << endl;
} 해법 2:
동적 계획 을 사용 하여 주로 양쪽 문자 에서 비교 합 니 다. dp [i] [j] 는 아래 표 시 된 i 에서 j 까지 의 하위 문자열 이 답장 문자열 에 삽입 할 문자열 의 길이 가 되 어야 한 다 는 것 을 표시 합 니 다.
만약 s [i] = s [j], 그러면 dp [i] [j] = dp [i + 1] [j - 1]
그렇지 않 으 면 dp [i] [j] = min (dp [i + 1] [j], dp [i] [j - 1] + 1, 왜 dp [i + 1] [j] 와 dp [i] [j - 1] 일 까요? 머리 끝 이 일치 하지 않 는 것 을 발견 할 때마다 머리 나 꼬리 에 대응 하 는 떨 어 진 문 자 를 추가 하면 리 턴 문자열 을 구성 하 는 목적 을 달성 할 수 있 기 때 문 입 니 다. 그 중의 모든 하위 문제 에 대해 서 는 이 렇 습 니 다.
코드 는 다음 과 같 습 니 다:
#include
#include
using namespace std;
const int MAX_SIZE = 5005; //
short dp[MAX_SIZE][MAX_SIZE]; //dp[i][j] [i, j] ， “ ”
int main()
{
int n;
cin >> n;
string str;
cin >> str;
/* ， 0， */
for(int i = n - 1; i >= 0; i--) {
for(int j = i; j <= n - 1; j++) {
if(str[i] == str[j])
dp[i][j] = dp[i + 1][j - 1];
else
dp[i][j] = getMin(1 + dp[i][j-1], 1 + dp[i+1][j]);
}
}
cout << dp[0][n-1] << endl;
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
