C++でパリンドローム部分文字列を繰り返し削除した後に文字列を削除するための最小手順

問題の説明

文字のみを整数として含む文字列を指定します。この文字列のすべての文字を最小限のステップで削除する必要があります。1つのステップで、回文である部分文字列を削除できます。サブストリングを削除した後、残りの部分が連結されます。

例

入力文字列が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