7447. Обрезка строки

Имеется строка s. Разрешается взять два любых одинаковых соседних символа и удалить их из строки. Эту операцию можно производить пока имеется возможность. Сначала Вы можете выбрать любое количество символов в строке и удалить их. Определить наименьшее количество символов, которое Вы можете удалить сначала так, чтобы затем выполняя разрешенную операцию, получить пустую строку.

Вход. Содержит строку s (1 ≤ длина(s) ≤ 100).

Выход. Вывести наименьшее количество символов, которое следует удалить сначала.

Пример входа	Пример выхода
abacdeec	2

РЕШЕНИЕ

динамическое программирование

Анализ алгоритма

Пусть dp[l][r] = f(l, r) – наименьшее количество символов, которое следует удалить из подстроки s_l..s_r, чтобы далее в результате применения операций (удаление одинаковых соседних символов) можно было получить пустую строку. Тогда:

· f(l, r) = 0, если l > r;

· f(l, l) = 1, единственный символ следует удалить сначала;

· f(l, r) = f(l + 1, r – 1), если s[l] = s[r]. Если крайние символы одинаковы, то следует удалить внутреннюю часть, после чего эти символы станут соседними и их можно будет удалить применением операции;

· f(l, r) = 1 + f(l + 1, r), если мы удаляем первый символ;

· f(l, r) = 1 + f(l, r – 1), если мы удаляем последний символ;

Однако два последних условия можно включить в следующее: для решения задачи на отрезке [l; r] решим задачу отдельно на отрезках [l; i] и [i + 1; r] (l ≤ i < r) и возьмем наименьший результат:

f(l, r) =

Например, случай удаления из строки первого символа эквивалентен i = l (тогда f(l, l) = 1), а случай удаления последнего символа эквивалентен i = r – 1 (f (r, r) = 1).

Ответом на задачу будет dp[0][n – 1] = f(0, n – 1), где n – длина входной строки.

Пример

Рассмотрим пример, приведенный в условии. Имеем:

f(0, 7) = f(0, 2) + f(3, 7) = 1 + 1 = 2

Реализация алгоритма

Объявим используемые массивы.

#define MAX 101

#define INF 0x3F3F3F3F

int dp[MAX][MAX];

string s;

Пусть f(l, r) – решение задачи на отрезке [l; r].

int f(int l, int r)

{

if (l > r) return 0;

if (l == r) return 1;

if (dp[l][r] != INF) return dp[l][r];

int &res = dp[l][r];

if (s[l] == s[r])

res = min(res, f(l + 1, r - 1));

for (int i = l; i < r; i++)

res = min(res, f(l, i) + f(i + 1, r));

return res;

}

Основная часть программы. Читаем строку.

cin >> s;

memset(dp,0x3F,sizeof(dp));

Вычисляем и выводим ответ f(0, n – 1), где n – длина строки s.

printf("%d\n",f(0, s.size() - 1));

Java реализация

import java.util.*;

public class Main

{

static String s;

static int dp[][];

static int f(int l, int r)

{

if (l > r) return 0;

if (l == r) return 1;

if (dp[l][r] != Integer.MAX_VALUE) return dp[l][r];

int res = dp[l][r];

if (s.charAt(l) == s.charAt(r))

res = Math.min(res, f(l + 1, r - 1));

for (int i = l; i < r; i++)

res = Math.min(res, f(l, i) + f(i + 1, r));

return dp[l][r] = res;

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

s = con.nextLine();

int n = s.length();

dp = new int[n][n];

for(int i = 0; i < n; i++)

for(int j = 0; j < n; j++)

dp[i][j] = Integer.MAX_VALUE;

System.out.println(f(0, n - 1));

con.close();

}

}