1. Задача о кузнечике со стоимостями.
Пусть кузнечик прыгает на одну или две точки вперед, а за прыжок в каждую точку необходимо заплатить определенную стоимость,
различную для различных точек.
Стоимость прыжка в точку i задается значением Price[i] списка Price. Необходимо найти минимальную стоимость маршрута кузнечика
из точки 0 в точку n.
На этот раз нам необходимо модифицировать определение целевой функции.
Пусть C(n) — минимальная стоимость пути из 0 в n.
Выведем рекуррентное соотношение для C(n).
Чтобы попасть в точку n мы должны попасть в точку n − 1 или n − 2.
Минимальные стоимости этих маршрутов будут равны C(n − 1) и C(n − 2) соответственно, к ним придется добавить значение Price[n]
за прыжок в клетку n.
Но из двух клеток n − 1 и n − 2 нужно выбрать тот маршрут, который имеет наименьшую стоимость.
Получили рекуррентное соотношение:
C(n) = min(C(n − 1), C(n − 2)) + Price(n).
Вычислить значение целевой функции также лучше при помощи динамического программирования, а не рекурсии:
Пример на языке Python
C = [0] * (n + 1)
C[1] = Price[1]
for i in range(2, n + 1):
С[i] = min(C[i — 1], C[i — 2]) + Price[i]
Пример на языке Pascal
var
C, Price: array[0..100] of longint;
i, n: longint;
begin
readln(n);
for i := 1 to n do
read(Price[i]);
for i := 0 to n do
C[i] := 0;
C[1] := Price[1];
for i := 2 to n do
C[i] := min(C[i - 1], C[i - 2]) + Price[i];
writeln(C[n]);
end.
После выполнения этого цикла в списке С будет записана минимальная стоимость маршрута для всех точек от 0 до n.