分治和動(dòng)態(tài)規(guī)劃：

共同點(diǎn)：

兩者都是把大問題轉(zhuǎn)換成小問題/子問題來解決，并且當(dāng)最優(yōu)子問題組合成最優(yōu)大問題，關(guān)鍵點(diǎn)在于找到子問題的劃分。

不同點(diǎn)：

分治采用遞歸寫法，當(dāng)子問題之間沒有重復(fù)的時(shí)候，是很好的方法，但當(dāng)子問題之間存在重復(fù)的時(shí)候，分治方***重復(fù)計(jì)算子問題很多次，碰到一次算一次，因?yàn)榉种问亲陨隙碌模伦叩倪^程中，每次碰到相同的子問題都要重復(fù)計(jì)算，時(shí)間復(fù)雜度很高。動(dòng)態(tài)規(guī)劃，專門針對(duì)這種存在重復(fù)子問題的分解算法，并且每一個(gè)大問題都可以由它的子問題的最優(yōu)解來表示；因此，動(dòng)態(tài)規(guī)劃采用自下而上的方法，先計(jì)算最小的子問題的最優(yōu)解，再一層層組合成大問題的最優(yōu)解，計(jì)算過程中不存在子問題的重復(fù)計(jì)算。