自上而下DP的自下而上DP

Question

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

我们能否想出一些机制,它给出了自上而下的DP可以转换为自下而上DP的正式方式.

注意:我是动态编程的初学者,我所看到的自顶向下方法转换为自下而上方法的问题很少.所以我不确定是否可以采用通用方法.

通过概括我的意思是,应该如何初始化数组,应该是数组的大小以及数组应该具有多少维度.

Answer 1

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

Answer 2

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