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

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

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

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

textual
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.

11   голосов, оценка 4.182 из 5


СОХРАНИТЬ ССЫЛКУ