소문자와 정수 k를 포함하는 문자열 s가 있다고 가정합니다. 우리는 일부 속성을 유지해야 합니다. 이들은 -
- 먼저 s의 일부 문자(필요한 경우)를 다른 소문자 영어로 변경해야 합니다.
- 그런 다음 문자열 s를 k개의 하위 문자열로 나누어 각 하위 문자열이 회문(palindrome)이 되도록 합니다.
문자열을 나누기 위해 변경해야 하는 최소 문자 수를 찾아야 합니다.
따라서 문자열이 "ababbc"이고 k =2이면 답은 1이 됩니다. 왜냐하면 이것을 두 개의 회문 문자열로 나누기 위해 한 문자를 변경해야 하기 때문입니다. 따라서 c를 b로 변경하거나 두 번째 마지막 b를 c로 변경하면 "bbb" 또는 "cbc"와 같은 하나의 회문을 얻을 수 있고 다른 회문은 "aba"가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 105 x 105 크기의 배열 메모를 정의합니다.
- solve() 함수를 정의하면 s, idx, k, 하나의 2D 배열> dp,
- idx가 s의 크기와 같으면 -
- k가 0이면 0을 반환하고 그렇지 않으면 1000을 반환
- memo[idx][k]가 -1과 같지 않으면 -
- 반품 메모[idx][k]
- k <=0이면 -
- 반환 정보
- ans :=inf
- 초기화 i :=idx의 경우, i <크기가 s인 경우 업데이트(i를 1만큼 증가), −
- ans :=ans 및 dp[idx][i]의 최소값 + 함수 solve(s, i + 1, k - 1, dp) 호출
- 반환 메모[idx][k] =as
- 메인 방법에서 다음을 수행합니다.
- n :=s의 크기
- -1로 메모 채우기
- n x n 크기의 2D 배열 dp 하나 정의
- 초기화 l :=2의 경우 l <=n일 때 업데이트(l을 1씩 증가), 수행 -
- 초기화 i :=0, j :=l - 1, j
- l이 2와 같으면 -
- dp[i][j] :=s[i]가 s[j]와 같지 않을 때 참
- 그렇지 않으면
- dp[i][j] :=dp[i + 1][j - 1] + s[i]가 s[j]와 같을 때 0
- 초기화 i :=0, j :=l - 1, j
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
int memo[105][105];
lli solve(string s, int idx, int k, vector < vector <int> > &dp){
if(idx == s.size()) {
return k == 0? 0 : 1000;
}
if(memo[idx][k] != -1) return memo[idx][k];
if(k <= 0)return INT_MAX;
lli ans = INT_MAX;
for(int i = idx; i < s.size(); i++){
ans = min(ans, dp[idx][i] + solve(s, i + 1, k - 1, dp));
}
return memo[idx][k] = ans;
}
int palindromePartition(string s, int k) {
int n = s.size();
memset(memo, -1, sizeof(memo));
vector < vector <int> > dp(n, vector <int>(n));
for(int l =2; l <= n; l++){
for(int i = 0, j = l - 1; j <n; j++, i++){
if(l==2){
dp[i][j] = !(s[i] == s[j]);
}else{
dp[i][j] = dp[i+1][j-1] + !(s[i] == s[j]);
}
}
}
return solve(s, 0, k, dp);
}
};
main(){
Solution ob;
cout << (ob.palindromePartition("ababbc", 2));
} 입력
“ababbc”
출력
1