algorithm - 自下而上的 DP 从自上而下的 DP

Question

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

我们能否想出某种机制来提供正式的方式，通过这种方式我们可以将自上而下的 DP 转换为自下而上的 DP。

注意:我是动态规划的初学者，我见过的从自上而下方法转换为自下而上方法的问题很少有很大不同。所以我不确定是否可以采用通用方法。

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

Answer 1

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