hihocoder 1323 텍스트 문자열 구간 dp OR 기억화 검색
묘사
문자열 S를 지정하려면 최소한 몇 번의 삭제 작업이 필요합니다. S를 메모 문자열로 바꿀 수 있습니까?
한 번에 임의의 위치에 문자를 삽입하거나, 임의의 문자를 삭제하거나, 임의의 문자를 임의의 다른 문자로 수정할 수 있다.
아이디어:
기억화 검색을 고려하면 dp[l][r]는 l에서 r로 끝나는 문자열이 메모열을 구성하는 데 필요한 최소 작업 횟수를 나타낸다.
1. 만약에 s[l]=s[r]dp[l][r]=dp[l+1][r-1];
2.만약s[l]!=s[r]그러면 우리는 문자를 추가하고, 문자를 삭제하고, 문자를 수정하는 것을 고려해야 한다.문자를 삭제하고 추가하는 것이 사실 등가임을 감안하면
네, 여기 첨가만 할게요.
dp[l][r] = min(dp[l+1][r],dp[l][r-1],dp[l+1][r-1])+1
dp[l+1][r]는 s[r] 뒤에 s[l] 문자가 일치하는 것을 표시합니다
pp[l][r-1]는 s[1] 앞에 s[r] 문자가 일치하는 것을 나타낸다
pp[l+1][r-1]는 s[l]s[r] 중 하나를 다른 것으로 수정하는 것을 나타낸다.
#include
using namespace std;
const int N = 105;
int dp[N][N];
char s[N];
int min(int a, int b, int c)
{
return min(min(a, b), c);
}
int dfs(int l,int r)
{
if(l >= r) return dp[l][r] = 0;
if(dp[l][r] != -1) return dp[l][r];
if(s[l] == s[r])
return dp[l][r] = dfs(l+1,r-1);
return dp[l][r] = 1+min(dfs(l+1,r),dfs(l,r-1),dfs(l+1,r-1));
}
int main()
{
scanf("%s",s+1);
int len = strlen(s+1);
memset(dp, -1, sizeof(dp));
dfs(1,len);
cout< 물론 구간 dp도 가능하지만 사실은 위의 본질과 똑같다. 모두 가장 작은 (두 글자마다)로 회문을 구성하고 크게 확장한다.
#include
#include
#include
using namespace std;
char s[105];
int dp[105][105];
int min(int a,int b,int c)
{
return min(a,min(b,c));
}
int main()
{
scanf("%s", s);
int n = strlen(s);
for(int len = 2; len <= n; len++)
{
for(int i = 0; i + len - 1 < n; i++)
{
int j = i + len - 1;
if(s[i] == s[j])
dp[i][j] = dp[i+1][j-1];
else
dp[i][j] = min(dp[i+1][j],dp[i][j-1],dp[i+1][j-1]) + 1;
}
}
printf("%d
", dp[0][n-1]);
return 0;
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
