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