自下而上的DP

Question

我在想，是否有一种通用的方法将自上而下的动态编程转换为自下而上的编程。

我们能想到某种机制吗?这种机制给出了自上而下DP转换为自下而上DP的正式方式。

注意到：我是动态编程的初学者，我所见过的将自顶向下的方法转换为自下而上的方法的问题很少是完全不同的。因此，我不确定是否有一个广义的方法是可能的。

广义我的意思是，数组应该如何初始化，数组的大小应该是多少，数组应该有多少个维度。

Answer 1

动态程序的执行可以看作是一个有向无圈图，其中每个顶点都是一个子问题，弧表示需要对一个特定子问题的解决方案来计算另一个子问题的解。一个自上而下的递归程序所做的是，在本质上，通过深度优先搜索，从根本上对这个图的子图进行排序。要将其转换为自下而上的方法，您需要自己制定一个合适的拓扑顺序，这将因问题而异。

Answer 2

自顶向下的解决方案通常更好，因为它只解决必要的子问题。将自下而上的解决方案转换为自上而下的解决方案非常简单，您只需按需计算和存储子问题，而不是预先计算所有问题。另一种方法可能很棘手，因为您需要知道要解决哪些子问题。根据问题的不同，在不检查上层问题的情况下找到子问题的难度从容易到不可能不等。例如，考虑以下情况:您有一个无限着色的加权图，它的眩晕用10种颜色着色。从给定的一个垂直线到最近的蓝色垂直线的距离是多少？解决它是可能的，但自下而上是不可能的，因为你需要从图的所有蓝色眩晕开始。