C++の奇妙なプリンター

奇妙なプリンターがあるとしましょうそれはいくつかの要件があります-

• プリンタは、毎回同じ文字のシーケンスのみを印刷できます。
• 各ターンで、プリンタは任意の場所で開始および終了する新しい文字を印刷でき、元の既存の文字をカバーします。

したがって、文字列が小文字で構成されている場合、私たちのタスクは、それを印刷するためにプリンターが必要とする最小回転数をカウントすることです。

したがって、入力が「aaabba」のような場合は、2ターンかかります。最初に、文字を置き換えてaaaaaを出力し、次にbを出力します。

これを解決するには、次の手順に従います-

• n：=sのサイズ
• nが0と同じ場合、0を返します
• 次数nxnの1つの2D配列dpを定義し、これを無限大で埋めます
• 初期化l：=1の場合、l <=nの場合、更新（lを1増やします）、実行-
  • 初期化i：=0、j：=l --1の場合、j
  • lが1と同じ場合、dp [i、j]：=1
• それ以外の場合、lが2と同じ場合、-
  • dp [i、j]：=s[i]がs[j]と同じ場合は1、それ以外の場合は2
• それ以外の場合
  • kを初期化する場合：=i、k
  • temp：=dp [i、k] + dp [k + 1、j]
  • dp [i、j]：=最小のdp [i、j]および（s[k]がs[j]と同じ場合はtemp– 1、それ以外の場合はtemp。

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
class Solution {
public:
   int strangePrinter(string s) {
      int n = s.size();
      if(n == 0) return 0;
      vector < vector <int> > dp(n, vector <int>(n, INF));
      for(int l = 1; l <= n; l++){
      for(int i = 0, j = l - 1; j < n; i++, j++){
         if(l == 1){
            dp[i][j] = 1;
            }else if(l == 2){
               dp[i][j] = s[i] == s[j] ? 1 : 2;
            }else{
               for(int k = i; k < j; k++){
                  int temp = dp[i][k] + dp[k + 1][j];
                  dp[i][j] = min(dp[i][j], s[k] == s[j] ? temp - 1: temp);
               }
            }
         }
      }
      return dp[0][n - 1];
   }
};
main(){
   Solution ob;
   cout << (ob.strangePrinter("aaabba"));
}

入力

“2*”

出力

2