「動態」編程與「正常」編程有什麼不同？

每當我看到電腦競賽的解決方案，我總是看到術語「動態編程」。我搜索了這個術語並閱讀了一些文章，但沒有一篇提供了一個編程VS「動態」編程的簡單例子。那麼「動態」編程與「正常」編程有什麼不同呢？（請簡單條款！）「動態」編程與「正常」編程有什麼不同？

來源

2012-02-28 Leo Jiang

動態編程實際上可能意味着一些不同的事情。 – SLaks 2012-02-28 22:58:14

[什麼是動態規劃？]可能的重複（http://stackoverflow.com/questions/1065433/what-is-dynamic-programming） – DNA 2012-02-28 23:01:00

參見http://stackoverflow.com/questions/1540848/a-simple - 對於想要了解動態規劃的人來說，這是一個例子 – DNA 2012-02-28 23:01:25

Dynamic Programming使用編程更多在與Linear Programming使用的意義 - 解決問題的機制。

一個描述最近，我讀（但不能再回想源 - [引證需要]）建議，在recursion使用divide and conquer的通常的方法是解決問題的自上而下的方法，而動態編程是自下而上的解決問題的方法。

維基百科的文章建議計算Fibonocci sequence是動態規劃的一個很好的用處 - 你計算它們的結果以供在算法中進一步使用，以避免重新計算類似的結果。

Knuth's algorithm for line-breaking paragraphs是動態規劃的另一個很好的例子：如果你考慮插入換行符每一個字之間（甚至斷裂線內的話，在斷字點）的可能性，那感覺就像唯一的算法將是指數 - - 或更糟。然而，通過記錄與先前換行符相關的「不良」，Knuth算法實際上在線性時間下運行，其輸入大小。（我必須承認，我不完全瞭解Knuth的算法 - 只是它非常聰明。）

來源

2012-02-28 23:10:22 sarnold

通過「正常」編程，我想你的意思是C++/Java/C＃編程吧？

從這個意義上講，動態規劃不是「編程」。這不是關於編寫代碼的問題，而是「編程」這個詞在解決複雜問題的過程中使用，將它們分解爲更簡單的問題。

來源

2012-02-28 22:58:41 CodeBlue

它與基於分而治之的編程類似嗎？ – Faizan 2013-02-18 18:43:51

動態編程並不是真正的「編程」，而是查表[和存儲] - 這犧牲了一點空間以提高時間複雜性[相當多]。

來源

2012-08-28 07:41:54 Fakrudeen

我知道這是一箇舊帖子，但我有同樣的問題，所以我在這裏回答我自己。

動態規劃有兩個屬性：

最優子：一個全局最優解可以通過最優解決方案，以本地子問題結合中找到。例如，FIB（X）= FIB（X - 1）+ FIB（X - 2）
重疊子問題：找到的最優解涉及同樣的問題多次解決。例如，Fibonocci序列中多次計算fib（x）

通過以上定義/屬性，不清楚某些問題如「是否屬於一個集合」？或者「如何找到一套的總和」可以歸類爲動態規劃？我可以將該集合劃分爲子集（全局求解）並添加它（獲得全局答案）。此外，在子集內，我多次進行求和。

我在書中找到了一段，我認爲它提供了非常有用的技巧來區分「動態編程」（DP）和「分而治之算法」（D & C）。

在D & C子問題中，它們明顯小於原始問題。相比之下，DP涉及解決僅比原始問題略小的問題。例如，計算Fib（19）並不比計算Fib（20）小得多。儘管十個元素的計算總和實際上小於一千萬個元素的總和。
效率D & C算法不依賴於構造算法，以便重複解決相同的問題。相反，只有當不同的子問題的數量明顯小於子問題的總數時，DP纔有效。

來源

2017-04-16 04:45:48 Ying

「動態」編程與「正常」編程有什麼不同？

回答

相關問題