C ++中的奇怪打印机

假设有一台奇怪的打印机，它有一些要求-

• 打印机每次只能打印相同字符的序列。

• 在每一回合中，打印机都可以打印从任何地方开始和在任何地方结束的新字符，并且将覆盖原来的现有字符。

因此，如果我们的字符串由小写字母组成，则我们的任务是计算打印机打印所需的最少转数。

因此，如果输入类似“ aaabba”，则将花费2圈，首先打印aaaaa，然后通过替换字符打印b。

为了解决这个问题，我们将遵循以下步骤-

• n：= s的大小

• 如果n与0相同，则：返回0

• 定义一个nxn阶的2D数组dp，并用无穷大填充

• 对于初始化l：= 1，当l <= n时，更新（将l增加1），-

• 对于初始化k：= i，当k <j时，更新（k增加1），做-

• temp：= dp [i，k] + dp [k + 1，j]

• dp [i，j]：= dp [i，j]的最小值，并且（当s [k]与s [j]相同时为temp – 1，否则为temp。

• dp [i，j]：= 1，当s [i]与s [j]相同时，否则为2

• 如果l与1相同，则：dp [i，j]：= 1

• 对于初始化i：= 0，j：= l-1，当j <n时，更新（i增加1），（j增加1），-

• 否则，当l与2相同时，则-

• 除此以外

• 返回dp [0，n-1]

让我们看下面的实现以更好地理解-

示例

#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