Динамическое программирование.Удаление строки

[zaptos91]

Дана строка S, состоящая из n маленьких латинских букв. За один ход Вам разрешается удалить один или несколько подряд идущих одинаковых символов. Необходимо удалить все символы из строки S за минимальное количество ходов.

Буду признателен за разъяснение алгоритма для данной задачи,учитывая,что её нужно решать методами динамического программирования. Я в нём абсолютный ноль, так что надеюсь тема не будет удалена из-за отсутствия кода.Я сам его напишу,мне нужны советы по поводу алгоритма решения. Заранее спасибо.

[zaptos91]

Я так понял,что нужно в матрицу NxN (N -размерность строки) начиная с главной диагонали,вписывать количество минимальных удалений для подстрок длины 1,2 и т.д
Подскажите формулу перехода для таких состояний.


Я надеюсь на форуме кто-нибудь в состоянии мне помочь?

[zaptos91]

#include <iostream>
#include <fstream>
using namespace std;

int MIN(int x,int y)
{
	if(x<y) return x;
	return y;
}

int main()
{
char S[300];

ifstream in("input.txt");
in>>S;
in.close();

  
int n = strlen(S);
int **A = new int*[n];
for(int i = 0; i < n; i++)
A[i] = new int[n];


for(int i=0;i<n;i++)//главную диагональ заполним 1,остальное - нулями
for(int j=0;j<n;j++){
    if(i!=j)
	A[i][j]=0;
	else
    A[i][i]=1;
}

for (int k = 1; k < n; k++) {//в цикле - если у подстроки символы начала и конца совпадают,достаточно рассмотреть задачу 
    for (int i = 0; i + k < n; i++) {//удаления символов между совпадающими,иначе - рассматриваем две подстроки
        int j = i + k;
        if (S[i] == S[j])
			A[i][j] = MIN(A[i+1][j], A[i][j-1]);
        else 
			A[i][j] = MIN(A[i+1][j], A[i][j-1]) + 1;
    }
}



}
ofstream out("output.txt"); 
out<<A[0][n-1];//Ответ
out.close();

return 0;
}

___________
Код нужно оформлять по правилам:
тегом [CODE]..[/СODE] (это кнопочка с решёточкой #)
Не забывайте об этом!
Модератор.

[Johnson]

в Си не силен, могу помочь только с логикой...

читаем символ Х
пока Х+1 равен по значению Х то удаляем Х+1, и входим в новую интерацию ЭТОГО цикла.
когда Х и Х+1 не равны - инкрементим Х, и начинаем заново, если не достигнут конец строки.

Если нужно могу написать пример на паскале...

[zaptos91]

Напиши,если не трудно. Хотя мне кажется,идея не верна - на строке

авсрра - у тебя будет 4 хода?

[phomm]

Вообще, задача тут довольно не тривиальная... как объяснить железной башке, что человек специально может задавать такие аццкие строки...

Думаю, сперва надо произвести посчет количества каждой буквы и удаление одиночных символов(т.е. совем одиночный а не одиночно стоящих), ну тут многие догадаются ))
потом, думаю, можно подсчитать группы одинаковых символов, т.е. подряд идущих. ну и по идее организовать цикл по всем этим группам, где рекурсивно вызывать такой же цикл (но уже с удаленной на предыдущем шаге группой) и счетом величины стека рекурсии... в итоге каждая рекурсия долна вернуть величину шагов по вызову самой себя, если мы начнем с некоей группы.

Запутанно, конечно.. и не четко условие выбора группы на каждом шаге рекурсии.

Ещё есть идея, но даже не знаю как она будет работать... сделать процедуру которая считает за сколько шагов можно сделать самую большую группу символов, ну и проверяем если удаление мвалых подгрупп этих символов выгоднее чем составление большой группы, то переходим к рассмотрению задачи для следующей максимально-символьной группе, но с уже удаленными символами предыдущей группы. Минус сего метода, наверное, в том что промежуточное составленние группы (т.е. не максимально возможной) мб выгоднее, чем удаление малых групп...

[Johnson]

авсрра - у тебя будет 4 хода?

s:='abcppa';
for I:=length(s) downto 2 do begin
	if s[I]=s[I-1] then Delete(S,I,1);	
end;

5 ходов... Меньше не вижу возможности.

Этот алгоритм уберет только первый повторяющийся символ... В каждом проходе.

[zaptos91]

Сообщение от Johnson

s:='abcppa';
for I:=length(s) downto 2 do begin
	if s[I]=s[I-1] then Delete(S,I,1);	
end;

5 ходов... Меньше не вижу возможности.

Этот алгоритм уберет только первый повторяющийся символ... В каждом проходе.

4хода - убираем b->c->pp->aa

Народ,помогите довести до ума код,защитил алгоритм у преподавателя,а нормальная реализация не выходит.

Алгоритм - пусть в строке S содержится N символов. Создаём матрицу NxN,на главной диагонали расставляем единицы-кол-во удалений для подстроки длины 1,на диагонали над главной - 2,или 1 в зависимости от того,состоит ли подстрока длинны 2 из одинаковых или разных символов.
Далее, увеличивая длины подстрок, пользуемся следующими формулами:

А(i,j)-подстрока,внутри неё бегаем по К
Если S(i)!=S(k),то в матрицу =>
A(i,j)=1+A(i+1,j)

Иначе - S(i)==S(k) -в матрицу =>
A(i,j)=MIN(A(i+1,k-1)+A(k,j)

Таким образом,в правом верхнем углу матрицы будет ответ.

[zaptos91]

#include <iostream>
#include <fstream>
using namespace std;

int main()
{
char S[300];

ifstream in("input.txt");
in>>S;
in.close();

  
int n = strlen(S);
int **A = new int*[n];
for(int i = 0; i < n; i++)
A[i] = new int[n];

for(int i=0;i<n;i++)
for(int j=0;j<n;j++){
    if(i!=j)
	A[i][j]=0;
	else
    A[i][i]=1;//главная диагональ
}
for(int i=0;i<n-1;i++)//заполнение диагонали над главной
{
if(S[i]==S[i+1])
A[i][i+1]=1;
else
A[i][i+1]=2;


}


bool flag;


for(int i=2;i<n;i++){
for(int j=0;j<n-i;j++){
	flag=true;
for(int k=j+1;k<i+j;k++){
	 if(S[k]==S[j]){
		 if(flag)
          A[j][i+j]=A[j+1][k-1]+A[k][i+j];
		  flag=false;
		  if(A[j][i+j]>=(A[j+1][k-1]+A[k][i+j]))//применение алгоритма к
                                                                  //последующим подстрокам
		  A[j][i+j]=A[j+1][k-1]+A[k][i+j];
		
	     }
	if(S[k]!=S[j])
		 A[j][i+j]=1+A[j+1][i+j];
}
}
}

cout<<A[0][n-1];//Ответ


return 0;
}

[Summer_Time]

zartos91, мне кажется, у Вас что-то не так. Например:

abcba - очевидно, что 3 удаления, но Ваш код выдал 4.
acdcbbc - 4 удаления - у Вас 6.
и т.д.