8.9. Чему вы научились

В этом разделе вы познакомились с основами динамического программирования — одного из самых мощных приёмов в алгоритмике. Вы поняли, как разбивать сложные задачи на подзадачи, хранить уже найденные решения и использовать их повторно. А главное — научились видеть в задачах структуру, подходящую под динамику.

Теперь вы умеетеТеперь вы умеете

• замечать подзадачи и формулировать рекуррентные соотношения;
• строить таблицы значений (в одну или несколько строк или столбцов) и переходов между ними;
• оптимизировать память и избегать повторных вычислений;
• решать задачи разными способами: с мемоизацией, итерацией, через восстановление ответа;
• применять динамическое программирование в практических задачах — от редактирования строк и поиска LCS до рюкзака и оптимального размещения скобок.

Что дальшеЧто дальше

В следующем разделе вы познакомитесь с другой идеей — «Разделяй и властвуй». Эта стратегия открывает путь к более эффективным алгоритмам для сортировки, поиска и анализа данных.