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