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

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

Пример:

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

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

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

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

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

😎 Решение:

var minChangesToMakePalindrome = function(s, k) {
    const n = s.length;

    const minChangeToPalindrome = (i, j) => {
        let changes = 0;
        while (i < j) {
            if (s[i] !== s[j]) {
                changes++;
            }
            i++;
            j--;
        }
        return changes;
    };

    const dp1 = Array.from({ length: n }, () => Array(n).fill(0));
    for (let length = 1; length <= n; length++) {
        for (let i = 0; i <= n - length; i++) {
            let j = i + length - 1;
            dp1[i][j] = minChangeToPalindrome(i, j);
        }
    }

    const dp2 = Array.from({ length: n + 1 }, () => Array(k + 1).fill(Infinity));
    dp2[0][0] = 0;

    for (let i = 1; i <= n; i++) {
        for (let kk = 1; kk <= k; kk++) {
            for (let 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];
};

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