是否总是存在对应记忆方法的动态规划自下而上的解决方案
Does there always exist a dynamic programming bottom up solution for corresponding memoization method
我搜索了一些现有的文本，例如
Dynamic programming and memoization
但我仍然无法得出结论。
Memoization 看起来很容易实现。但是对应的DP解法很费脑子。有时，我无法通过DP范式找到解决方案。
我想知道如果一个问题通过记忆解决（自上而下的方法），是否强制存在 DP 自下而上的解决方案？
是的，每个具有自上而下解决方案的动态规划问题也都有相应的自下而上动态规划解决方案。
您可以通过将任何 DP 问题的状态 space 可视化为 DAG 来证明这一点，节点代表状态，边代表节点之间的依赖关系。例如，如果 DAG 中存在从 A 到 B 的边，则意味着要获得状态 A 的解决方案，我们必须先解决状态 B。
因此，自下而上求解问题等同于按 topological sort.
的相反顺序对 DAG 的顶点应用动态规划
在某种程度上，是的，但细节可能很繁琐。
自下而上和自上而下方法的主要区别在于我们预先知道遍历状态 space 的顺序。
如果您正在探索具有深度优先搜索的图形（这是记忆本质上所做的），则存在该图形的顶点完成处理的顺序（计算并记忆顶点的值).可以通过对图进行拓扑排序来找到此顺序。然后，您可以按该顺序计算值，这可以看作是自下而上。
仍然，对于某些图，没有与图一致的拓扑顺序并且可以用简单方式表达（如for (row) for (col) calc (row, col)）。
自下而上的另一个问题是，对于自上而下的解决方案，我们只访问了我们实际需要计算的状态，它们的数量可能远远少于状态的总数。
加法。 此外，对于某些算法，顺序是根据我们计算的值即时计算的。
举个简单的例子，Dijkstra's algorithm可以看作是动态规划，但是顶点加入最短路径树的顺序取决于我们计算的距离。
因此，我们必须以一种或另一种方式找到所有最短距离才能找到顺序，因此在找到顺序后任何自下而上的解决方案都变得不必要了。
我搜索了一些现有的文本，例如 Dynamic programming and memoization
但我仍然无法得出结论。
Memoization 看起来很容易实现。但是对应的DP解法很费脑子。有时，我无法通过DP范式找到解决方案。
我想知道如果一个问题通过记忆解决（自上而下的方法），是否强制存在 DP 自下而上的解决方案？
是的，每个具有自上而下解决方案的动态规划问题也都有相应的自下而上动态规划解决方案。
您可以通过将任何 DP 问题的状态 space 可视化为 DAG 来证明这一点，节点代表状态，边代表节点之间的依赖关系。例如，如果 DAG 中存在从 A 到 B 的边，则意味着要获得状态 A 的解决方案，我们必须先解决状态 B。
因此，自下而上求解问题等同于按 topological sort.
的相反顺序对 DAG 的顶点应用动态规划在某种程度上，是的，但细节可能很繁琐。
自下而上和自上而下方法的主要区别在于我们预先知道遍历状态 space 的顺序。
如果您正在探索具有深度优先搜索的图形（这是记忆本质上所做的），则存在该图形的顶点完成处理的顺序（计算并记忆顶点的值).可以通过对图进行拓扑排序来找到此顺序。然后，您可以按该顺序计算值，这可以看作是自下而上。
仍然，对于某些图，没有与图一致的拓扑顺序并且可以用简单方式表达（如for (row) for (col) calc (row, col)）。
自下而上的另一个问题是，对于自上而下的解决方案，我们只访问了我们实际需要计算的状态，它们的数量可能远远少于状态的总数。
加法。 此外，对于某些算法，顺序是根据我们计算的值即时计算的。 举个简单的例子，Dijkstra's algorithm可以看作是动态规划，但是顶点加入最短路径树的顺序取决于我们计算的距离。 因此，我们必须以一种或另一种方式找到所有最短距离才能找到顺序，因此在找到顺序后任何自下而上的解决方案都变得不必要了。