Динамическое программирование, или просто динамика - метод решения задач, использующий решение меньших задач. Ознакомьтесь с примером. Он очень прост, но помогает понять принцип решения подобных задач.
Задача "Кузнечик":
Кузнечик находится в точке A с координатой (0). Он может за один прыжок преодолеть одну, две или три клетки. Сколькими способами он сможет добраться, двигаясь только вперед, до точки B с координатой (n)? n-целое, 0< n <51
Решение:
Заведем массив a[-2..50], где каждое a[i] показывает, сколькими способами можно добраться до точки с координатой i из точки 0. Сразу введем a[-2]:=0, a[-1]:=0, a[0]:=1. Т.к. в точку i можко добраться из точек i-3, i-2 и i-1, то a[i]=a[i-3]+a[i-2]+a[i-1]. Заполним таблицу, перебрав все числа от 1 до n. Ответом будет являться a[n].
program p1;
var
i,n:longint;
a:array[-2..50] of longint;
begin
read(n);
a[-2]:=0;
a[-1]:=0;
a[0]:=1;
for i:=1 to n do a[i]:=a[i-3]+a[i-2]+a[i-1];
write(a[n]);
end.
