Які обмеження на значення N, K, час та пам'ять?

А ось обмеження жорстокі. Обмеження
2 сек., 256 МіБ

Хоча якщо різниця між кроками може бути різною... Цей момент треба уточнити.

1≤ N, K ≤100

Ні, я про те, що шлях, де всі кроки по 3, потрапляє і в область 1:3, і в 2:3, і в 3:5.
Наступна ідея. Оскільки N і K маленькі, робимо для кожної сходинки замість одного числа A[ i ] - таблицю по мінімальних-максимальних кроках:
Сходинка I
Кількість шляхів сюди із кроком:
Min\Max 1  2  3  4  5   6  ... N
1           1  3  ...
2           -   1  ...
3           -   -  ...

На кожному наступному кроці, відповідно, заповнюємо всю таблицю по всіх можливих шляхах.
Очевидно, що нижня половина таблиці (Max<Min) та верхній трикутник (Max-Min>K) нам не потрібні.
Також для сходинки i не потрібна частина з Max>i.
Витрати пам'яті O(k*n^2) < 100^3 = 10^6, в 256МіБ вкладаємося; час, відповідно - O(k*n^3) < 100^4 = 10^8, тут жорсткіше, але маємо в 2с вкластися, всі операції - додавання, а у нас тільки половину таблиць заповнювати.
Детальніше розжовувати?

Ні.
Ще раз, як іде рішення, якщо у нас немає "правила Зеника": ми для кожної сходинки створюємо окрему змінну (тобто в результаті виходить одновимірний масив), який по одному кроку заповнюємо:
на першу сходинку можна потрапити 1 способом,
на другу - 2 (з землі і 1-ї сходинки), 
на третю - 4 (з землі, 1-ї сходинки і 2-ї сходинки з її 2-ма шляхами)
і т.д.
А тепер нам треба для кожної сходинки створити не одну змінну, а двовимірний масив, і заповнювати його аналогічно:
на i-у сходинку можна потрапити з землі кроком в i, це комірка A[ i ][ i ][ i ] (індекси: номер сходинки, мінімум, максимум); можна потрапити зі сходинки 1 кроком в i-1, це комірка A[ i ][1][i-1] і т.д.
Якщо ми розглядаємо, скільки існує способів переходу зі сходинки j на сходинку i, то нам доведеться для кожної комірки сходинки j (A[j][minj][maxj], де minj та maxj - змінні циклів, якими ми ітеруємо по таблиці сходинки j) подивитися, куди потрапляє нове значення i-j - якщо воно вписується в minj...maxj, то значення додається до A[ i ][minj][maxj]; якщо не вписується - то, наприклад, якщо більше за maxj, це буде додано до A[ i ][minj][i-j].

Так це ж найцікавіше.

В умові написано "скiлькома способами можна подолати N сходинок", а не "щонайменше N сходинок".

Ok, n=4, k=1. Без "правила Зеника" відповідь 8: (1,1,1,1), (1,1,2), (1,2,1), (2,2), (2,1,1), (1,3), (3,1), (4). Із ним - 6, бо (1,3) і (3,1) не проходять. Додаємо ваш цикл - треба врахувати всі шляхи з min,max = [1,2], [2,3] і [3,4]:
[1,2]: (1,1,1,1), (1,1,2), (1,2,1), (2,2), (2,1,1)
[2,3]: (2,2)
[3,4]: (4)
Разом - 7 шляхів. Чому? Бо шлях (2,2) входить у діапазони і [1,2], і [2,3].

Тобто розв’язуємо примаючи умову, що треба опинитись на сходинці N.