Задача на ДП.

[frankenstein]

Задача звучит так:
Обозначим через $A$ подмножество множества всех перестановок чисел
$\{ 1, 2, 3, ..., N \}$, для элементов которого истинны следующие утверждения:
Первое число $1$,
разница между любыми соседними числами не превышает $2$.

Дано: $N$
Требуется найти $|A|$

Я немножко подумал, и вот что решил:
Задача относится к семейству задач динамического программирования, значит должна быть
какая-та рекуррентная формула. Но вот найти ее не могу.
Вот решение задачи перебором для $N \le 12$

f(1) = 1
f(2) = 1
f(3) = 2
f(4) = 4
f(5) = 6
f(6) = 9
f(7) = 14
f(8) = 21
f(9) = 31
f(10) = 46
f(11) = 68
f(12) = 100

Решения надо найти для $N \le 55$.

[ИСН]

A038718 же.

[frankenstein]

Ну, тут все готовое дано, а мне именно надо освоить метод динамического программирования.
Хотя один человек сказал мне, что каждая задача дп. уникальна и что невозможно сводить
эти задачи к решенным, но я с ним несогласен, думаю можно разобрать несколько задач и
освоить технику.

[Cash]

Думаю, ваш знакомый всё же ближе к истине
Конкретно, на OEIS решение дано:

Join[{a=1, b=1, c=2}, Table[d=a+c+1; a=b; b=c; c=d, {n, 100}]]