Гирлянда без длинных серий

Гирлянда состоит из n лампочек в ряд, каждая включена или выключена. Чтобы она не слепила, нельзя, чтобы подряд горели k или больше лампочек. Верните, сколько существует различных рядов из n лампочек, в которых нет k включённых подряд. Для n = 0 ряд один (пустой). Ограничения: n от 0 до 30, k от 1 до 10.

Смотрите на то, сколько включённых лампочек стоит в конце ряда: от 0 до k - 1. Добавление лампочки либо обнуляет эту серию, либо увеличивает её на единицу.

Пример: 3, 2 → 5 (000, 001, 010, 100, 101).

Источник: задача CodeShare