Динамическое программирование

Главное

Задачу разбивают на подзадачи и сохраняют их ответы. Пример: число программ исполнителя — сумма числа программ для предыдущих чисел.

Правила

1. Считаем от меньших к большим
2. f(n) = f(n − 1) + f(n / 2) и т. п.
3. Храним ответы в массиве

Разберём пример

Команды +1 и ×2. Сколько программ из 1 в 4?

4 (в число 2 можно попасть двумя способами)

Частые ошибки

• Считать повторно уже решённые подзадачи.

Потренироваться

Задания с проверкой и подсказками, схема темы и разбор ошибок с ИИ-репетитором — в уроке на платформе.