Сигнал задачи
Когда применять
Подзадачи перекрываются, а ответ определяется малым состоянием.
Что держать в голове
- Уметь выбирать достаточное состояние DP.
- Уметь объяснять устранение повторных рекурсивных вызовов мемоизацией.
Сложность
- Время обычно равно числу достижимых состояний, умноженному на число переходов; память — числу хранимых состояний.
Границы и ошибки
- Состояние должно содержать всю информацию для будущего и не хранить лишнюю историю; порядок вычисления обязан уважать зависимости.