Сложность: hard
Существует странный принтер с двумя особыми свойствами:
Принтер может печатать последовательность одного и того же символа за раз.
На каждом шагу принтер может печатать новые символы, начиная и заканчивая в любом месте, при этом покрывая уже существующие символы.
Дана строка s. Верните минимальное количество ходов, необходимых для её печати.
Пример:
Input: s = "aaabbb"
Output: 2
Explanation: Print "aaa" first and then print "bbb".
👨💻 Алгоритм:
1⃣Инициализация и подсчет:
Создайте двумерный массив dp, где dp[i][j] представляет минимальное количество ходов для печати подстроки s[i:j+1].
2⃣Динамическое программирование:
Если s[i] == s[j], тогда dp[i][j] = dp[i][j-1], так как последний символ совпадает с предыдущим.
В противном случае, dp[i][j] = min(dp[i][k] + dp[k+1][j]) для всех i <= k < j, чтобы найти минимальное количество ходов.
3⃣Возврат результата:
Возвратите dp[0][n-1], где n - длина строки s, что представляет минимальное количество ходов для печати всей строки.
😎 Решение:
class Solution:
def strangePrinter(self, s: str) -> int:
n = len(s)
dp = [[0] * n for _ in range(n)]
for length in range(1, n + 1):
for i in range(n - length + 1):
j = i + length - 1
dp[i][j] = dp[i][j-1] + 1
for k in range(i, j):
if s[k] == s[j]:
dp[i][j] = min(dp[i][j], dp[i][k] + (dp[k+1][j-1] if k + 1 <= j - 1 else 0))
return dp[0][n-1]
Ставь 👍 и забирай 📚 Базу знаний