Какие задачи решают методом динамического программирования?

Шаг один: поймите идею на самом простом примере — числах Фибоначчи. Каждое число там равно сумме двух предыдущих: 1, 1, 2, 3, 5, 8, 13. Если считать наивно через обычную рекурсию, программа при вычислении, скажем, восьмого числа заново пересчитывает третье и четвертое числа десятки раз внутри разных веток вызовов, хотя ответ там один и тот же каждый раз. Шаг два: динамическое программирование решает это за счет запоминания уже посчитанных подзадач. Посчитали третье число один раз — записали результат в таблицу или массив, и дальше просто берете готовое значение вместо повторного счета. Шаг три: разница в скорости растет вместе с размером входных данных, это и есть смысл понятия сложности, или Big O. Наивная рекурсия для чисел Фибоначчи растет экспоненциально: каждое увеличение номера числа почти удваивает число операций. Версия с запоминанием растет линейно: на каждое число тратится примерно одна дополнительная операция. На маленьких числах разницы не видно, но чем больше вход, тем сильнее наивный вариант отстает, счет там может идти на секунды и минуты, где версия с запоминанием отвечает почти мгновенно, точных цифр по времени я не привожу, они сильно зависят от железа. Шаг четыре: классические примеры для практики — задача о рюкзаке, где нужно набрать вещи максимальной ценности в ограниченный вес, и поиск кратчайшего пути, где выгоднее пройти через промежуточную точку, чем напрямую. Оба сводятся к тому же принципу: большая задача раскладывается на маленькие повторяющиеся, и результат каждой маленькой задачи считается один раз. Главная ошибка новичков на собеседовании — пытаться сразу писать динамическое решение. Проще сначала написать наивную рекурсию, она обычно короче и понятнее, а затем добавить запоминание результатов, увидев, какие подзадачи повторяются.