- Динамическое программирование позволяет отыскать оптимальное решение, когда какой-нибудь параметр будет максимальным или минимальным.
- Пример. Кузнечик сидит в клетке 1 и может прыгать вправо на 1 или 3 клетки. За прыжок в каждую клетку нужно заплатить определённую стоимость (элементом Price [i] массива Price задаётся стоимость прыжка в клетку i). Найдите минимальную стоимость маршрута в клетку N.
Программный код (фрагмент основного алгоритма) с комментариями:
Cтрока кода | Комментарий |
|---|---|
for i := 1 to N do C [i] := 0; | Заполняем массив начальными нулевыми значениями |
C [2] := Price [2]; | Стоимость прыжка в клетку 2 |
C [3] := C [2] + Price [3]; | Стоимость прыжка в клетку 3 (единственный путь из клетки 2) |
for i := 4 to N do C [i] := min (C [i - 3], | Стоимость прыжка в клетку i склады-вается из стоимости i-й клетки и мини-мальной из возможных накопленных стоимостей маршрутов из (i – 1)-й или (i – 3)-й клеток |
Writeln (C [N]); | Минимальная стоимость маршрута в клетку N |