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