Окружность на ней точки обозначены буквами A,B,C,D. Дается строка(порядка 200 букв) с произвольным наборов букв (количество А и B совпадает, С и D тоже совпадает). Надо найти количество способов соединить все точки непересекающимися хордами. Если А можно соединить только с B(и обратно можно B c A), С только с D(D можно с C). 
Я ее решил рекурсией, но не подходит из-за времени выполнения. 
Не понимаю как с помощью динамического программирования решить. Помогите.

p.s. я python использую

Это сообщение отредактировал(а) hter - 11.12.2013, 16:08

не пойму, при чём тут динамическое программирование
но если вы найдёте такое решение, отпишитесь, пожалуйста

возможно, вы делаете полный перебор, а можно сократить
соединять можно только те точки A и B, между которыми, двигаясь по окружности, количество точек A совпадает с количеством точек B, и количество C совпадает с количеством D

Может быть, проще переписать уже имеющееся решение на чем-то другом? У Python'а, при всех его достоинствах, скорость выполнения крайне низкая, даже замена на другой интерпретируемый язык может оказаться достаточной.

Отпишусь, но как то я далек от этого.
Я не все перебираю, а только которые остались.




Может быть, но O(n^3). Если б в строке было 10-20 символов то не проблема, а в строке их 200 и более. 
на чем попробовать советуете?

Это сообщение отредактировал(а) hter - 13.12.2013, 17:55

В идале - на чистом C. В реальности лучше сначала прикинуть, насколько надо увеличить быстродействие.

А как решали? Надо так - проводим хорду, далее считаем ответ для левой и правой половин, перемножаем. И, разумеется, ответы сохраняем, чтобы по нескольку раз их не считать. Такой алгоритм и с такими ограничениями, как мне кажется, и на питоне будет быстро работать.

hter, а есть последовательности, на которых можно потестироваться, чтоб заведомо было решение

Одних первых хорд может быть э так вариантов 100.
Я решал по кругу..от первого и перебрал какие подходят

Добавлено через 4 минуты и 13 секунд


Так можно и придумать:

CACBADBDCDAB - 2 варианта
АBABAB - 5 вариантов
АBABСDAB - 1 вариант

Ну и что? Всего состояний в динамике 100 * 199, а каждое большее состояние просчитывается за O(n) через меньшие (уже подсчитанные и сохраненные), а значит общая сложность - куб. Тормозить в данной реализации может только сам питон 

Вот что значит сохраненные?

Добавлено через 59 секунд
Может мой нубский код скинуть?

Добавлено через 4 минуты и 22 секунды
ну должно же быть решение не за O(n^3) а там за O(nlogn)

Почему должно?   Тем более на таких ограничениях n^3 вполне приемлем.


Что-то типа псевдокода c синтаксисом C++ 


Это - вполне себе динамика, только записанная в рекурсивной форме.

Для каждой пары входных параметров функции, если уже считали ответ, возвращаем его сразу.

Спасибо, попробую реализовать.



ну как то хочется, что б было))

Добавлено через 28 секунд

жаль си не знаю

Что непонятного в этом псевдокоде? Убрать int и скобки {} - почти питон будет  

так вроде должно быть 200 букв 
просто случайно сгенерированная последовательность из 200 у меня имеет не более 5 возможных (с учётом правила из моего первого комментария) хорд из одного узла, а для некоторых узлов ни одного

На случайных ответ чаще всего 0 будет  А на правильно подобранных - очень большое число.

Тут, кстати, 5 вариантов.