Задача: 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 MinChangeToPalindrome(string s, int i, int j) {
            int changes = 0;
            while (i < j) {
                if (s[i] != s[j]) {
                    changes++;
                }
                i++;
                j--;
            }
            return changes;
        }

        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 i = 0; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                dp2[i, j] = int.MaxValue;
            }
        }
        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];
    }
}

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