自上而下DP自上而下DP

Question

我在想，是否有一些將自上而下的動態編程轉換爲自下而上編程的一般方法。

我們是否可以考慮一些機制，通過這種機制，可以將自上而下的DP轉換爲自下而上的DP。

注意：我是動態程序設計的初學者，很少遇到一個自頂向下方法轉換爲自下而上方法的問題，這兩者有很大的不同。所以我不確定是否可以採用一般化的方法。

通過泛化我的意思是，應該如何初始化數組，應該是數組的大小和數組應具有多少維數。

Answer 1

動態程序的執行可以看作是一個有向無環圖，其中每個頂點都是一個子問題，弧指示需要解決特定子問題來計算另一個子問題的解決方案。帶有記憶的自頂向下的遞歸程序實際上是通過深度優先搜索從根本問題的拓撲排序圖的子圖。爲了將其轉換爲自下而上的方法，您需要自己制定合適的拓撲順序，這些順序因問題而異。

Answer 2

Top Down解決方案通常更好，因爲它只解決必要的子問題。將自下而上的解決方案轉換爲自上而下非常簡單，您只需按需計算和存儲子問題，而不是預先計算所有子問題。另一種方法可能會很棘手，因爲您需要知道要解決哪些子問題。根據問題的不同，在不檢查上層問題的情況下查找子問題的困難可能很容易變成不可能。例如，請考慮以下幾點：您擁有無限的彩色加權圖形，並且其垂直着色爲10種顏色。什麼是從給定的A verticle到最近的藍色垂直線的距離。解決它是可能的，但自下而上不可能，因爲您需要從圖形的所有藍色垂直圖像開始。