矩阵链乘法如何成为 DAG 中最短路径的特例？
How is Matrix Chain Multiplication a special case of shortest path in DAG?
矩阵链乘法的DP算法可以建模为DAG中的最短路径吗？我在某处读到每个 DP 问题都是在隐式 DAG 上行走，但我无法想象那些转换导致多个状态（或子状态）的问题。
还有一个我未能形象化的例子是 UVA 10003. A DP solution of the above is discussed here: Cutting a stick such that cost is minimized。
想象一下，如果我们可以从第一个状态转到第二个状态，则两个状态之间存在一条有向边（当然，一个状态可以由多个参数组成）。这个图中没有环，所以是DAG。因此，可视化 DAG 本身并不难（您只需写下它们之间的所有状态和边即可）。但是没有必要可以建模为最短路径搜索。例如，在关于割绳子的问题中，状态的值是其他两个状态的值之和，因此它甚至不是路径。无论如何，如果参数的数量非常大，将解决方案可视化可能是不切实际的。并且不需要做任何可视化来解决一个问题并证明你的解决方案的正确性。
矩阵链乘法的DP算法可以建模为DAG中的最短路径吗？我在某处读到每个 DP 问题都是在隐式 DAG 上行走，但我无法想象那些转换导致多个状态（或子状态）的问题。
还有一个我未能形象化的例子是 UVA 10003. A DP solution of the above is discussed here: Cutting a stick such that cost is minimized。
想象一下，如果我们可以从第一个状态转到第二个状态，则两个状态之间存在一条有向边（当然，一个状态可以由多个参数组成）。这个图中没有环，所以是DAG。因此，可视化 DAG 本身并不难（您只需写下它们之间的所有状态和边即可）。但是没有必要可以建模为最短路径搜索。例如，在关于割绳子的问题中，状态的值是其他两个状态的值之和，因此它甚至不是路径。无论如何，如果参数的数量非常大，将解决方案可视化可能是不切实际的。并且不需要做任何可视化来解决一个问题并证明你的解决方案的正确性。