DP на DAG
DP на DAG
Введение
Многие задачи динамического программирования можно представить в виде ориентированного ациклического графа (DAG).
- вершины DAG → подзадачи / состояния
- рёбра DAG → переходы
Связь DP и DAG
Подзадачи = вершины DAG
В динамическом программировании задача разбивается на подзадачи.
Каждая подзадача соответствует состоянию.
В DAG:
Переходы = рёбра DAG
Если из состояния можно перейти в состояние , то в DAG есть ребро:
