動態編程基礎


難度級別 容易獎學金
經常問 印孚瑟斯 空氣質量
動態編程 理論

在動態編程基礎知識中,我們將介紹DP的基礎知識及其與貪婪方法,分而治之和遞歸的區別。

動態編程是一種類似於遞歸,分而治之的方法。 它將問題分為多個子問題。 但是,與其使用諸如分而治之和遞歸之類的方法獨立解決這些子問題,不如將先前子問題的結果用於相似的計算(也稱為重疊問題)。

用於優化程序。 由於它使用先前計算的結果,因此使用它的指數時間複雜度可以簡化為多項式。 例如–醜數的遞歸解的時間複雜度是指數的,而DP解的遞歸時間是線性的。

DP的一些基本問題

  • 醜數問題
  • 硬幣找零
  • 斐波納契數
  • 響鈴號碼問題
  • 河內塔
  • 鈴號
  • 背包問題

動態編程(DP)與貪婪方法

在DP中,每個步驟都要考慮當前以及先前的解決方案來評估解決方案,以獲得最佳解決方案。 但是,在貪婪算法中,我們僅考慮當前情況選擇最佳選項。

儘管貪婪方法通常比DP更快,並且由於不存儲先前計算出的值以備將來使用,因此內存使用效率也很高,但它不能保證最佳解決方案。

動態編程(DP)與分而治之方法

在分而治之中,我們將問題分為子問題,並獨立解決每個子問題。 但是,在DP中,我們將先前獲得的結果用於新的計算,而不是獨立地解決問題。 換句話說,我們可以說分而治之+記憶化=自上而下的動態方法。

(備忘是指通常將以前計算的結果存儲在哈希圖中以防止一遍又一遍地計算相同問題的技術。)

動態編程(DP)vs遞歸方法

DP會存儲先前計算的解決方案,以備將來再次使用時避免再次計算。 但是,在遞歸中,有可能進行重新計算,這是不必要的,因為它不存儲值。

遞歸導致問題的重新計算多次,因此在這種情況下,遞歸的時間複雜度始終大於DP解決方案。

在本文中,我們討論了 動態編程 基本。 在接下來的文章中,我們將介紹DP的一些基本問題。

參考文獻 面試問題