数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中的奇怪打印机
假设有一台奇怪的打印机，它有一些要求：
- 打印机每次只能打印相同字符的序列。
- 在每次打印中，打印机可以从任何位置开始和结束打印新字符，并将覆盖原始存在的字符。
因此，如果我们有一个由小写字母组成的字符串，我们的任务是计算打印该字符串所需的最小打印次数。
例如，如果输入是“aaabba”，那么它将需要 2 次打印，首先打印 aaaaa，然后替换字符打印 b。
为了解决这个问题，我们将遵循以下步骤：
- n := s 的大小
- 如果 n 等于 0，则：返回 0
- 定义一个大小为 n x n 的二维数组 dp，并将其填充为无穷大
- 初始化 l := 1，当 l <= n 时，更新（l 加 1），执行：
- 初始化 i := 0，j := l - 1，当 j < n 时，更新（i 加 1），（j 加 1），执行：
- 如果 l 等于 1，则：dp[i, j] := 1
- 否则，当 l 等于 2 时，则：
- 当 s[i] 等于 s[j] 时 dp[i, j] := 1，否则 2
- 否则
- 初始化 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）的最小值。
- 初始化 k := i，当 k < j 时，更新（k 加 1），执行：
- 初始化 i := 0，j := l - 1，当 j < n 时，更新（i 加 1），（j 加 1），执行：
- 返回 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
更新于: 2020年6月1日
230 次浏览
广告