動態規劃：自上而下與自下而上比較

Question

您能否指出一些動態規劃問題的陳述，其中自下而上比上自下而上更有利？ （即簡單的DP工作更自然，但memo化將更難實施？）

我發現遞歸與memoization更容易，並希望解決問題，自下而上是一個更好的或許只有可行的方法。

我知道理論上兩者都是等價的，所以即使是易於實現的東西也可以算作一種好處。

Answer 1

根據手頭的問題，您將使用memoization自上而下地應用自上而下的遞歸。

例如，如果您必須找到路徑圖的最小權重無關路徑，那麼您將使用自下而上的方法，因爲您必須解決所有可能的子問題。

但是，如果你必須解決揹包問題，你可能希望使用遞歸自上而下，因爲你必須解決有限數量的子問題。自下而上處理揹包問題會導致算法解決很多未在原始子問題中使用的冗餘問題。

Answer 2

兩件事情來決定使用哪種算法

1. 時間複雜度時需要考慮的。這兩種方法通常具有相同的時間複雜度，但是因爲循環比遞歸函數調用便宜，所以如果在機器時間中測量，則自下而上可以更快。
2. 空間複雜性。 （在自上而下不考慮額外調用堆棧分配的情況下）通常，這兩種方法都需要爲所有子解決方案構建一個表格，但自下而上是遵循拓撲順序，其輔助空間的成本有時可能會減少到問題的大小直接依賴關係。例如：fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)，我們只需要存儲在過去的兩個計算

話雖這麼說，自底向上的並不總是最好的選擇，我會嘗試用例子來說明：

1. （自提by @Nikunj Banka）自上而下僅解決您的解決方案使用的子問題，而自下而上可能會浪費時間解決冗餘的子問題。一個愚蠢的例子是0-1 knapsack與1項...運行時間差是O（1）與O（重量）
2. 您可能需要執行額外的工作才能獲得拓撲訂單。在Longest Increasing Path in Matrix，如果我們希望自己的依賴後做的子問題，我們就必須按照從大到小的順序矩陣的所有條目進行排序，這是DP
之前額外 nmlog(nm)預處理時間