Лестница с выбитыми ступенями

В подъезде n ступеней, они пронумерованы снизу вверх числами от 1 до n; пол под первой ступенью считается ступенью 0. За один шаг можно подняться на 1, 2 или 3 ступени вверх. Некоторые ступени выбиты (их номера даны в списке broken): вставать на них нельзя, но перешагивать через них можно. Верните, сколькими разными последовательностями шагов можно подняться с пола на ступень n. Если n = 0, ответ 1 (шагов не нужно); если ступень n выбита, ответ 0.

Значение для ступени i естественно выразить через последний шаг: сколько способов добраться до i - 1, i - 2 и i - 3. Ограничения: n не больше 30.

Пример: 3, [] → 4 (1+1+1, 1+2, 2+1, 3).

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