664. Strange Printer
Đề Bài
There is a strange printer with the following two special properties:
- The printer can only print a sequence of the same character each time.
- At each turn, the printer can print new characters starting from and ending at any place and will cover the original existing characters.
Given a string s, return the minimum number of turns the printer needed to print it.
Example 1:
Input: s = "aaabbb" Output: 2 Explanation: Print "aaa" first and then print "bbb".
Example 2:
Input: s = "aba" Output: 2 Explanation: Print "aaa" first and then print "b" from the second place of the string, which will cover the existing character 'a'.
Constraints:
1 <= s.length <= 100sconsists of lowercase English letters.
Thuật Toán & Kỹ Thuật
⏱️ Thời gian
O(n×m)
💾 Không gian
O(n×m)
Lời Giải
C++
0664-strange-printer.cpp
class Solution {
private:
string s;
public:
int memo[101][101];
int dp(int i, int j) {
if (j < i) {
return 0;
}
if (i == j) {
return 1;
}
if (memo[i][j] != -1) {
return memo[i][j];
}
int ans = 1 + dp(i + 1, j);
for (int k = i + 1; k <= j; ++k) {
if (s[i] == s[k]) {
ans = min(ans, dp(i + 1, k - 1) + dp(k, j));
}
}
return memo[i][j] = ans;
}
int strangePrinter(string s) {
this->s = s;
memset(memo, -1, sizeof(memo));
int n = s.size();
return dp(0, n - 1);
}
};
Python
0664-strange-printer.py
class Solution:
def strangePrinter(self, s: str) -> int:
n = len(s)
@lru_cache(None)
def dp(l, r):
if l > r:
return 0
ans = 1 + dp(l + 1, r)
for k in range(l + 1, r + 1):
if s[l] == s[k]:
ans = min(ans, dp(l + 1, k - 1) + dp(k, r))
return ans
return dp(0, n - 1)