Определить число всевозможных "маршрутов" мячика с вершины на землю - PascalABC.NET

Формулировка задачи:

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

Входные данные

Вводится одно число 0 < N < 31.

Выходные данные

Выведите одно число — количество маршрутов.

Решение задачи: «Определить число всевозможных "маршрутов" мячика с вершины на землю»

Листинг программы

program dp1;
var
  dp : array[0..107] of uint64;
  n, i : integer;
  
begin
  readln(n);
  for i := 0 to 107 do dp[i] := 0;
  dp[n] := 1; //на n - ой ступеньке один способ - быть там вначале
  
  for i := n - 1 downto 0 do begin
    dp[i] := dp[i + 1] + dp[i + 2] + dp[i + 3]; //на i-ую ступетьку можно прыгнуть из i + 1, i + 2, i + 3
  end;
  
  //0 ступенька - земля => dp[0] - ответ.
  writeln(dp[0]);
end.

Объяснение кода листинга программы

В данном коде решается задача о числе всевозможных путей в глубину графа, представленная в виде стека (или очереди). Список действий:

Считывается из входных данных число n - количество уровней графа.
Создается массив dp размером 108 (включая нулевой элемент, который является землей).
Все элементы массива dp инициализируются нулем.
dp[n] устанавливается равным единице, так как на n-ой вершине только один путь - начать с нее.
Используя цикл, начиная с n-1 и до 0 (включительно), устанавливаются значения dp[i] равными сумме dp[i+1], dp[i+2] и dp[i+3]. Это обусловлено тем, что на i-ую вершину можно попасть только из i+1, i+2 или i+3.
Ответ (число путей до нулевой вершины) выводится на экран. Обратите внимание, что в данном коде предполагается, что граф направленный и без циклов (иначе пути не будут корректно учитываться). Также, для корректного выполнения программы, необходимо проверить, что n >= 0 и n <= 107.