何時使用自下而上的DP和何時使用自上而下的DP

Question

我有兩種DP的方式，但我現在很困惑。我們如何選擇不同的條件？我發現在大多數情況下，自頂向下對我來說更自然。誰能告訴我如何做出選擇。

PS：我已閱讀此帖子older post但仍然感到困惑。需要幫忙。不要將我的問題確定爲重複。我提到他們是不同的。我希望知道如何從自上而下或自下而上的方式選擇以及何時考慮問題。

Answer 1

爲簡單起見，我將解釋根據我總結的一些sources

1. 自頂向下：東西看起來像：a(n) = a(n-1) + a(n-2)。有了這個公式，你可以通過調用自己的函數a來實現大約4-5行代碼。正如您所說，它的優勢對於大多數開發人員來說非常直觀，但它需要更多的空間（內存堆棧）來執行。
2. 自下而上：你第一個計算a(0)然後a(1)，並將其保存到某個數組（例如），然後你連續保存a(i) = a(i-1) + a(i-2)。採用這種方法，您可以顯着提高代碼的性能。與大n，你可以避免堆棧溢出。

Answer 2

如果你喜歡自然自然然後使用它，如果你知道你可以實現它。自下而上比自上而下的要快。有時底部起伏更容易，大多數時候底部起伏很容易。根據你的情況做出你的決定。

Answer 3

自下而上和自上而下的DP方法在時間和空間複雜度方面的許多問題都是相同的。不同的是，自下而上快一點，因爲你不需要額外的遞歸，而且自上而下更直觀自然。

但是，上下方法的真正優勢可以放在一些小的任務上，你不需要爲所有較小的子任務計算答案！在這種情況下你可以減少時間複雜性。

例如，您可以使用自頂向下的方法找到第N個斐波納契數，其中序列定義爲[n] = a [n-1] + a [n-2]有兩個O（N）時間來計算它（我沒有比較O（logN）解決方案找到這個數字）。但是看一下序列a [n] = a [n/2] + a [n/2-1]以及一些小N的邊緣情況。在botton up方法中，你不能做得比O（N）快自上而下的算法將複雜度爲O（logN）的工作（或者一些聚對數的複雜性，我不知道）