Задача: 1278. Palindrome Partitioning III
Сложность: hard

Вам дана строка s, содержащая строчные буквы, и целое число k. Вам нужно: Сначала заменить некоторые символы s на другие строчные английские буквы. Затем разделить s на k непустых непересекающихся подстрок так, чтобы каждая подстрока была палиндромом. Верните минимальное количество символов, которое нужно изменить, чтобы разделить строку.

Пример:

Input: s = "abc", k = 2
Output: 1

👨‍💻 Алгоритм:

1⃣Используйте динамическое программирование для вычисления количества изменений, необходимых для превращения любой подстроки в палиндром.

2⃣Используйте еще одно динамическое программирование для разбиения строки на k палиндромических подстрок с минимальным количеством изменений.

3⃣Верните минимальное количество изменений, найденное во втором шаге.

😎 Решение:

public class Solution {
    public int minChangesToMakePalindrome(String s, int k) {
        int n = s.length();
        
        int[][] dp1 = new int[n][n];
        for (int length = 1; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                dp1[i][j] = minChangeToPalindrome(s, i, j);
            }
        }

        int[][] dp2 = new int[n + 1][k + 1];
        for (int[] row : dp2) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }
        dp2[0][0] = 0;

        for (int i = 1; i <= n; i++) {
            for (int kk = 1; kk <= k; kk++) {
                for (int j = 0; j < i; j++) {
                    dp2[i][kk] = Math.min(dp2[i][kk], dp2[j][kk - 1] + dp1[j][i - 1]);
                }
            }
        }

        return dp2[n][k];
    }

    private int minChangeToPalindrome(String s, int i, int j) {
        int changes = 0;
        while (i < j) {
            if (s.charAt(i) != s.charAt(j)) {
                changes++;
            }
            i++;
            j--;
        }
        return changes;
    }
}

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