Задача по информатике Вовочке надо построить забор из досок длиной в 14 метров. На каждый метр забора может быть прибито не более одной доски. Важным условием является то, что на первом и последнем метре забора обязано быть по доске. При этом Вовочка может не пропускать, пропускать 1 или 4 метра подряд (но не более), то есть на этих метрах он не прибивает доски. Необходимо помочь Вовочке посчитать - сколькими способами он сможет построить забор. Можно считать, что у него в распоряжении есть любое необходимое количество досок.

Предыдущий
вопрос Следующий
вопрос

Для решения этой задачи можно воспользоваться динамическим программированием.

Пусть dp[n] - количество способов построить забор длиной n метров.

Из условия задачи следует, что dp[1] = dp[14] = 1, так как на первом и последнем метрах должна быть прибита доска.

Далее, можно заметить, что если на n-м метре доска прибита, то на n-1 и n-2 метрах доски быть не может, так как нельзя пропускать более 4 метров. Иначе, если на n-м метре доска не прибита, то на n-1 метре доска должна быть прибита.

Таким образом, формула для dp[n] будет выглядеть следующим образом:
dp[n] = dp[n-1] + dp[n-3] + dp[n-4]

Используя эту формулу, заполним массив dp по очереди, начиная с dp[2] и заканчивая dp[14].

Python код для решения задачи:

Ответ: Существует 710 способов построить забор.