Лично я осилил ее несколько "с фланга", а не составлением динамики, то есть сбрутфорсил полным перебором решения для размерностей до 5-6, и через известную базу данных последовательностей получил формулу (к счастью, такая последовательность там была).

Вопрос номер 1: вообще, для мира спортивного решения "канает" такое решение? Я имею ввиду использование этой базы данных для решение задач, вместо честного вывода формулы.

Вопрос номер 2: в обсуждении этой задачи на Тимусе даются две динамики, смысл которых мне не удается пока постичь.

№1

a[i][1] = a[i - 1][1] + a[i - 1][2],
a[i][2] = a[i - 1][2] + a[i - 3][2]

№2

a[i][1] = a[i-1][1] + a[i-2][2]
a[i][2] = a[i-2][1] + 1

Может кто-нибудь просто словами проговорить физический смысл a[i,t] в обоих случаях? Ясно, что i - это длина ряда в текущей подзадаче, а вот что такое t?