C++에서 회문 하위 문자열을 반복적으로 삭제한 후 문자열을 삭제하는 최소 단계

문제 설명

문자를 정수로만 포함하는 문자열이 제공됩니다. 최소한의 단계로 이 문자열의 모든 문자를 삭제해야 하며, 한 단계에서 회문인 부분 문자열을 삭제할 수 있습니다. 부분 문자열을 삭제하면 나머지 부분이 연결됩니다.

예시

입력 문자열이 3441213이면 최소 2단계가 필요합니다.

• 먼저 문자열에서 121을 제거합니다. 이제 남은 문자열은 3443입니다.
• 회문이므로 나머지 문자열 제거

알고리즘

동적 프로그래밍을 사용하여 이 문제를 해결할 수 있습니다.

1. Let dp[i][j] denotes the number of steps it takes to delete the substring s[i, j]
2. Each character will be deleted alone or as part of some substring so in the first case we will delete the character itself and call subproblem (i+1, j)
3. In the second case we will iterate over all occurrence of the current character in right side, if K is the index of one such occurrence then the problem will reduce to two subproblems (i+1, K – 1) and (K+1, j)
4. We can reach to this subproblem (i+1, K-1) because we can just delete the same character and call for mid substring
5. We need to take care of a case when first two characters are same in that case we can directly reduce to the subproblem (i+2, j)

예시

#include <bits/stdc++.h>
using namespace std;
int getMinRequiredSteps(string str) {
   int n = str.length();
   int dp[n + 1][n + 1];
   for (int i = 0; i <= n; i++) {
      for (int j = 0; j <= n; j++) {
         dp[i][j] = 0;
      }
   }
   for (int len = 1; len <= n; len++) {
      for (int i = 0, j = len - 1; j < n; i++, j++) {
         if (len == 1)
            dp[i][j] = 1;
         else {
            dp[i][j] = 1 + dp[i + 1][j];
            if (str[i] == str[i + 1]) {
               dp[i][j] = min(1 + dp[i+ 2][j], dp[i][j]);
            }
            for (int K = i + 2; K <= j; K++){
               if (str[i] == str[K]) {
                  dp[i][j] =
                  min(dp[i+1][K-1] + dp[K+1][j], dp[i][j]);
               }
            }
         }
      }
   }
   return dp[0][n - 1];
}
int main() {
   string str = "3441213";
   cout << "Minimum required steps: " <<
   getMinRequiredSteps(str) << endl;
   return 0;
}

위의 프로그램을 컴파일하고 실행할 때. 다음 출력을 생성합니다.

출력

Minimum required steps: 2