資料結構
網路
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 次瀏覽
廣告