Задача: Мячик на лестнице

Условие:

На вершине лесенки, содержащей $N$ ступенек, находится мячик, который начинает прыгать по ним вниз, к основанию. Мячик может прыгнуть на следующую ступеньку, на ступеньку через одну или через $2$. (То есть если мячик лежит на $8$-ой ступеньке, он может переместиться на $5$-ую, $6$-ую или $7$-ую.) Определить число всевозможных “маршрутов” мячика с вершины на землю.

Разбор решения:

Для начала нужно решить, как записать формулой варианты маршрута, если мячик стоит на неизвестной ступеньке $N$.

Есть три варианта: мячик прыгает на ступеньку $N - 1$, где у него будет некое число вариантов дальнейшего маршрута, может прыгнуть на ступеньку $N - 2$, где также будет свое количество вариантов, или на ступеньку $N - 3$, где у мячика тоже будут различные варианты дальнейшего пути. То есть можно утверждать, что количество вариантов для ступеньки $N$ – ничто иное как сумма чисел вариантов маршрута предыдущих ему ступенек, это можно записать формулой:

\[M_N = M_{N - 1} + M_{N - 2} + M_{N - 3}\]

Выведенная формула очень похожа на формулу нахождения числа Фибоначчи. Если мы закроем глаза на лестницу и мячик, то мы поймем, что это, также как и ряд Фибоначчи, последовательность вариантов маршрута, в которой тоже есть закономерность и рекуррентная формула.

Как и в прошлой задаче, составим таблицу:

$N$	1	2	3	4	5	i
решение	1	2	4	7	13	$M_i = M_{i - 1} + M_{i - 2} + M_{i - 3}$

Общая логика решения идентична решению задачи о последовательности Фибоначчи:

    vector<int> M(N+1);
    M[0] = 0; M[1] = 1; M[2] = 2; M[3] = 4;

    for (int i=2; i<=N; ++i) {
        M[i] = M[i-1] + M[i-2] + M[N-3];
    }
    cout << M[N] << '\n';

Теперь изначально мы добавили в таблицу три решения, потому что мы можем прыгать на три ступеньки вниз. Это обязывает нас рассмотреть решение для первых трех ступенек.

Если мячик стоит на первой ступеньке, то у него есть только один вариант – спрыгнуть вниз. Если мячик стоит на второй ступеньке, он может спрыгнуть на первую ступеньку, с которой можно спрыгнуть только одним способом, или сразу перепрыгнуть через ступеньку и спрыгнуть с лестницы – $2$ варианта. Если же мячик стоит на третьей ступеньке, он может спрыгнуть либо на вторую, откуда можно спрыгнуть двумя вариантами, либо сразу на первую, либо перепрыгнуть через две и спрыгнуть с лестницы – $4$ варианта.

Асимптотика данного решения есть $O(N)$.