단순 dp- 최소 문자를 삭제하고 메모 문자열로 바꾸기
문제풀이 사고방식: 여기에 두 가지 문제풀이 방법을 제공한다. 첫 번째는 전편에 쓴 LCS(최장 공공 서브열)를 사용하고 두 번째는 직접적인 dp이다.
1, 첫 번째 사고방식은 s2 변수를 신청하여 s2가 s1의 반전을 하게 하는 것이다. 만약에 회문열이라면 s2와 s1의 LCS를 구하는 것과 같다. 예를 들어 s1=abca, s2=acba, 공공 서브열의 길이는 3(aba,aca)이기 때문에 삭제해야 할 문자열의 개수는 4-3=1이다.LCS 접근 방식에 대한 자세한 내용은 이전 편에서 설명한 바와 같이 코드와 함께 제공됩니다.
#include
#include
#include
using namespace std;
string s1,s2;
int n;
int c[1000][1000];
int main()
{
cin >> s1;
n = s1.length();
s2 = s1;
reverse(s2.begin(), s2.end());
for (int i = 0; i <= n; i++)
{
c[i][0] = 0;
}
for (int j = 0; j <= n; j++)
{
c[0][j] = 0;
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (s1[i - 1] == s2[j - 1])
{
c[i][j] = c[i - 1][j - 1] + 1;
}
else
{
int ma = max(c[i - 1][j], c[i][j - 1]);
c[i][j] = ma;
}
}
}
cout << n-c[n][n] << endl;
return 0;
} 2. 두 번째 사고방식은 직접 추론하는 것이다. 여기는 2차원수 그룹 dp[i][j]를 사용해야 한다. 이곳의 i와 j는 아래에서 i에서 j로 표시된 하위 문자열에서 삭제해야 하는 문자 개수를 가리킨다.
분석: 만약에 dp[i][j]를 알고 있다면 s[i+1]=s[j+1], dp[i+1][j+1]=dp[i][j], 그렇지 않으면 dp[i+1][j+1]=min(dp[i+1][j], dp[i][j+1])+1.
주요한 사고방식은 먼저 길이가 1인 서브열을 초기화하는 것이다. 예를 들어 dp[0][0]=0, dp[1][1]=0, dp[2][2]=0......dp[n-1][n-1]=0;
그리고 길이가 1인 dp값을 통해 길이가 2인 서브열을 계산한다. dp[0][1], dp[1][2], dp[2][3]...dp[n-2][n-1];길이가 n으로 계속 미뤄졌을 때 dp[0][n-1]의 값이 답이다.그래서 모두 두 개의 순환이 필요하다. 외층 순환은 길이이고 내층 순환은 아래 표의 위치이다.
코드:
#include
#include
#include
using namespace std;
string s;
int n;
int dp[1000][1000];
int main()
{
cin >> s;
n = s.length();
for (int i = 0; i < n; i++)
{
dp[i][i] = 0;
if (s[i] == s[i + 1]&&i+1 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
01 가방, 완전 가방, 다중 가방 dp(동적 기획 입문 dp)01 가방은 2진법으로 직접 표시할 수 있지만 데이터 양이 너무 많으면 시간을 초과하는 것이 폭력이다.01 가방의 사상은 바로 이 물품에 대해 내가 넣은 가치가 큰지 안 넣은 가치가 큰지 비교하여 방정식 f[i][v...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
