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