算法中诅挑，動態(tài)規(guī)劃和分治算法是屬于兩種算法思想四敞，他們有相同點和不同點：
相同點：
1，兩者都是將大問題分解成若干個小問題拔妥，
2忿危，兩者都是依賴于小問題的解決，來解決上一級較大問題
不同點：
1没龙，分治法往往用到遞歸計算铺厨，自上而下計算缎玫，而動態(tài)規(guī)劃則直接自底向上計算
2，分治大的小問題在遞歸的過程中可能會被反復(fù)計算努释，動態(tài)規(guī)劃中的小問題計算后被存儲碘梢，下次再碰到時直接調(diào)用、
3伐蒂，分治法的小問題的解只使用一次煞躬，動態(tài)規(guī)劃的小問題的解存儲以備大問題求解時反復(fù)調(diào)用
動態(tài)規(guī)劃的一般構(gòu)造條件：
1，存在最優(yōu)子結(jié)構(gòu)：下一級的最優(yōu)解可以作為上一級最優(yōu)解的基礎(chǔ)
2逸邦，存在重復(fù)子問題：許多子問題的解會多次被調(diào)用（效率）
構(gòu)造方法：
從子問題出發(fā)恩沛，自底向上，構(gòu)造最優(yōu)解缕减，同時需要適配合適的數(shù)據(jù)結(jié)構(gòu)存儲子問題最優(yōu)解
Paste_Image.png
Paste_Image.png
Paste_Image.png
Paste_Image.png
Paste_Image.png
Paste_Image.png
Paste_Image.png
