🔒Открыть пост
и посмотреть медиа
и посмотреть медиа
Задача: 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
