Здравствуйте, Кузнец, Вы писали:

К>Либо 260 сложений этому алгоритму недостаточно, либо я его попросту неверно понял. Описанный алгоритм разлагает ответ в сумму единиц и их складывает, по-моему это в первом сообщении и описано (идёт рекурсия функцией f, рекурсивный вызов обрывается лишь если второй аргумент f равен нулю, при такой ситуации значение f будет равно 1, то есть внизу рекурсии у нас только единицы).

Это сейчас у тебя рекурсия написана, а в первом сообщении написано про динамику. В динамическом программировании не нужно повторно решать уже решенные задачи. Спуск до единиц произойдёт только при первом переходе от длины 0 к длине 1. Больше они никогда в решении не возникнут.

К> как именно должен выглядеть алгоритм.
Алгоритм — как написано. Простейшая реализация — так:

Пусть V - число состояний автомата

завести два массива A[V] и B[V]
инициализировать массив A значениями 0 или 1 в зависимости от того, является ли соответствующее состояние терминальным

для i от 1 до n:
   занулить массив B
   для каждой вершины v из [1..V]:
       для каждого символа s из алфавита:
           B[g(v, s)] += A[v]
   поменять массивы A и B местами
выдать A[root]