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

Не совсем понятно, как понять где пересекаются хорды, а где нет

Это наоборот понятно.
Пусть i,j - индексы пары точек(A,B или С,D). Тогда для следующей k,l должно быть k<i <j<l, или i<k<l<j или i<j<k<l или k<l<i<j. т.е. следующая пара должна лежать или внутри (i,j) или снаружи.
Мне не понятно как это сделать не перебирая каждую пару.
Например мы имеем строку АBABAB соответствует (0,1,2,3,4,5).
Тогда перебором получаем 5 вариантов:
0,1;2,3;4,5;
0,1;2,5;3,4;
0,3;1,2;4,5;
0,5;1,2;3,4;
0,5;1,4;2,3;
Перебрать 200^3 пар не реально. А как заполнить таблицу для динам. прог. я не втыкаю

Хм… у меня получается, только заполнить таблицу на места, где не проводятся хорды… Но как посчитать способы - без понятия… Задача интересная, надо подождать мастера динамического программирования, если таковой имеется

Да я заполнил ноликами(невозможно) и единичками(возможно). А дальше не понимаю. Если б были только A и B, то это элементарно (числа Каталана).