- Динамическое программирование – метод решения задач путём составления последовательности из подзадач:
- первая подзадача имеет простое решение;
- последний элемент этой последовательности – это исходная задача;
- каждая подзадача этой последовательности может быть решена с использованием решения подзадач с меньшими номерами.
- Отличия динамичного программирования от использования рекурсивных функций:
- промежуточные значения вычисляются в цикле и сохраняются в списке;
- список заполняется от меньших значений к большим;
- сложность алгоритма существенно ниже.
- Пример. Кузнечик сидит в клетке № 1 и может прыгать вправо на 1 или 3 клетки. Подсчитайте количество разных способов, которыми он может добраться до клетки N.
- Программный код (фрагмент основного алгоритма):
for (int i = 1; i < N + 1; i++)
F [i] = 0; // заполняем массив начальными нулевыми
значениями
F [1] = 1; // единственный путь для исходной 1-й клетки
F [2] = 1; // единственный путь для 2-й клетки
F [3] = 1; // единственный путь для 3-й клетки
for (int i = 4; i < N + 1; i++)
F [i] = F [i - 1] + F [i - 3]; // в i-ю клетку можно
попасть из (i-1)-й и (i-3)-й клеток
cout << F [N]; // количество различных путей добраться
до N-й клетки
Информатика • 9 класс
165
Динамическое программирование. Подсчёт количества вариантов (C++)
Было полезно?
Рекомендуем
Вы учитель или ученик?
Познакомьтесь с нашим образовательным онлайн-сервисом с тысячами интерактивных работ
Учителю
Удобно проводить уроки в классе, назначать работы на дом и анализировать результаты всего класса или конкретных учеников
Ученику
Самостоятельно изучать новые и повторять пройденные темы, готовиться по индивидуальной траектории и оценивать результаты на наглядных графиках