После прочтения материала на <a href="https://stackoverflow.com/questions/37661079/can-dynamic-programming-problems-always-be-represented-as-dag" rel="nofollow">SO</a> я немного запутался. Ранее я был уверен, что динамическое программирование всегда подразумевает отсутствие циклов. Если же циклы существуют, это приводит к зависимостям между вершинами, которые зависят от этих циклов, следовательно, такие задачи становятся невычислимыми. Как правильно понимать эту ситуацию?
Динамическое программирование (DP) действительно обычно ассоциируется с задачами, которые можно решить без циклов, поэтому их можно представить в виде направленного ациклического графа (DAG). В этом контексте "ацикличность" означает, что зависимость между подзадачами должна быть такой, чтобы мы могли вычислить их значения по порядку, что возможно только в DAG. Однако некоторые задачи могут вводить понятие "циклов" в ограниченном смысле, когда, например, текущее состояние может определяться предыдущими состояниями или подзадачами, которым при этом не обязательно нужно возвращаться. Например, в таких случаях мы можем использовать "мемоизацию" для сохранения уже вычисленных значений и избегать повторных вычислений, но сам процесс не будет являться "циклодинамическим программированием". Любая задача, в которой есть циклы в зависимости (например, задачи на графах с обратными путями), может быть сложно решить с использованием стандартного подхода к DP без предварительной обработки, такой как топологическая сортировка. Таким образом, можно сказать, что стандартные подходы динамического программирования предполагают отсутствие циклов (или принятие специальных мер для их обработки); аналогично, для большинства задач, рассматриваемых в рамках DP, существует DAG, который описывает персонажа зависимостей. Поэтому подход на основе DAG в контексте DP является правильным, но не всегда легко применимым к всем задачам, особенно к тем, где циклы могут иметь внешние последствия.
Тут вопрос определений. Что считать "представить в виде DAG".
В ДП можно составить граф зависимостей: какие состояния участвуют в вычислении каждого. Это будет DAG. Иначе у вас надо вычислять значения через самих себя и у вас уже не рекуррентные соотношения, а система уравнений.
В некоторых задачах эту систему уравнений можно решать иерархически, по частям, отдельно в каждой компоненте сильной связности. Это немного напоминает ДП, но им не является. Суть ДП в том, что у вас рекуррентные формулы. Это некий более общий алгоритм.
Если интерпретировать вопрос как: можно ли сформулировать задачу в виде "дан граф, подсчитать вот такую функцию в каждой вершине", то тут можно натянтуть сову на глобус, придраться к деталям и сказать, что нельзя. Именно это и говорится в SO.
Потому что иногда рекуррентные формулы не симметричные и вам надо, например, одно значение прибавить, другое вычесть. Это не всегда просто определить исключительно в терминах графа. Нельзя сказать что-то вроде "сложить значение во всех вершинах, куда ведут ребра". Но если добавить в этот граф пометки на ребрах или параметры состояний в вершинах, то можно задать нужную функцию (вроде: взять значение для вершины, в которую ведет ребро с пометкой 1 и вычесть значение из вершины, куда ведет ребро с пометкой 2).
Но эти помеченные графы все еще будут DAG.