Задача: 664. Strange Printer
Сложность: 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, что представляет минимальное количество ходов для печати всей строки.

😎 Решение:

public class Solution {
    public int strangePrinter(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        
        for (int length = 1; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                dp[i][j] = (i == j) ? 1 : dp[i][j - 1] + 1;
                for (int k = i; k < j; k++) {
                    if (s.charAt(k) == s.charAt(j)) {
                        dp[i][j] = Math.min(dp[i][j], dp[i][k] + (k + 1 <= j - 1 ? dp[k + 1][j - 1] : 0));
                    }
                }
            }
        }
        return dp[0][n - 1];
    }
}

Ставь 👍 и забирай 📚 Базу знаний