动态规划问题能否始终表示为 DAG

Question

我正在尝试为最长递增子序列 {3,2,6,4,5,1} 绘制 DAG，但无法将其分解为 DAG 结构。

是否可以在树状结构中表示这一点？

Answer 1

据我所知，标题中实际问题的答案是“不，并不是所有的DP程序都可以简化为DAG”。

将 DP 简化为 DAG 是我最喜欢的技巧之一，当它起作用时，它通常会给我对问题的关键见解，所以我发现它总是值得尝试。但我遇到过一些似乎至少需要超图的情况，这篇论文和相关研究似乎证明了这一点。

对于CS Stack Exchange来说，这可能是一个合适的问题，意味着有关图缩减的抽象问题，而不是有关最长递增子序列的具体问题。