動態規劃與分治之間的區別

分治與動態規劃的主要區別是什麼？如果我們舉一個例子，合併排序基本上是通過使用遞歸的分而治之來解決的。動態編程也基於遞歸，而不是合併排序被認爲是動態編程的一個例子？動態規劃與分治之間的區別

這兩者的相似之處在於它們都將問題分解爲小問題並解決問題。然而，在分而治之中，子問題是獨立的，而在動態規劃中，子問題是依賴的。既需要以某種方式重新組合的子問題，但區別來自子問題是否涉及到其他子問題

d & C例程（相同的「電平」的）：歸併

在歸併，你將排序分爲許多小的「子排序」，而不是排序100個項目，排序50個，然後排序25個等。然而，在將原始數據分解爲（例如）4個「子排序」之後，不管你先做什麼;訂單是無關緊要的，因爲它們是獨立的。重要的是他們最終會完成。因此，每一次，你都有一個完全獨立的問題，並有自己的正確答案。

DP例如：遞歸斐波納契

雖然有子問題，各自直接建立在另一個的頂部。如果你想要第10位數字，你必須以特定的順序來解決構建（1 + 2，2 + 3等）的問題。因此，他們不是獨立的。

2013-07-31 16:30:43 Daniel

像斐波那契數字一樣，下一個輸出取決於前一個輸出，所以我們稱之爲依賴序列。但是，在合併排序的情況下，我們不能說這個嗎？就像比較數字然後合併分區一樣？ – user2456752

@ user2456752請參閱我的編輯。如果這沒有幫助，讓我知道 – Daniel

可以解決的每個問題，都可以使用遞歸來解決。D＆C只是遞歸，將問題分解爲獨立的* peer *子問題。 DP只是遞歸，您可以多次重複使用某些子問題的解決方案*。爲了做到這一點，問題必須有兩個屬性，稱爲最佳子結構和重疊子問題。 –

D &當子問題是獨立的時候使用C.遞歸函數重複相同的遞歸調用時需要動態編程。

採取斐波納契復發：F（N）= F（N-1）+ F（N-2）

例如：

F（8）= F（7）+ F（6 ） =（f（6）+ f（5））+ f（6）

正如你可以看到f（6）將被計算兩次。從再現關係來看，顯然有太多的重複值。最好記住這些值，而不是反覆計算。在dp中最重要的是記住這些計算值。如果你看dp問題，通常使用數組或矩陣來防止重複計算。

與dp相比，d & c一般將問題分爲獨立的子問題和記憶任何值是不必要的。

2013-08-01 12:05:32 berk

所以，我要說的是d & C是一個更大的概念，DP是特殊的d的& C.具體而言，當你發現你的子問題需要共享同一個較小的子問題的一些計算，你可能不是他們希望一次又一次計算相同的內容，緩存中間結果以加快時間，這就是DP。所以，本質上，我會的方式，DP是D的快速版本D & C.

2014-08-26 06:04:43

回答