在基于劃分子問題的基礎(chǔ)上，衍生出兩種優(yōu)秀的方法——a. 動(dòng)態(tài)規(guī)劃 ?b. 備忘錄算法?

a. 動(dòng)態(tài)規(guī)劃的基礎(chǔ)是最優(yōu)子結(jié)構(gòu)———若一個(gè)大問題可以劃分成多個(gè)小問題，則在這多種劃分中，必有一種劃分，可使得作為宏觀問題，這種劃分得到的效果最優(yōu)；而在每個(gè)劃分出的子問題中，每個(gè)子問題也必有一個(gè)最優(yōu)劃分（否則用更好的劃分來代替原子問題的劃分，將會(huì)影響到宏觀結(jié)果） ? ?

動(dòng)態(tài)規(guī)劃的過程是利用子結(jié)構(gòu)，進(jìn)行自底而上的算法設(shè)計(jì)，應(yīng)為采用自底而上，故上面的問題依賴于下面問題的求解，下面的一些結(jié)果也直接提供給上層問題使用（作為上層問題的素材)。避免了重復(fù)計(jì)算（實(shí)際上采用自底向上的多循環(huán)結(jié)構(gòu)。利用多維數(shù)組存儲(chǔ)結(jié)果，就可以避免重復(fù)問題，舉個(gè)例子，就像設(shè)計(jì)一個(gè)高級(jí)算法，底層的算法諸如排序算法，一次編寫，可以供多個(gè)算法，多次使用）

弊處所在，就是沒有在處理的過程中實(shí)時(shí)的進(jìn)行處理，達(dá)到理想效果，而是用多次循環(huán)計(jì)算，用另外一個(gè)數(shù)組存儲(chǔ)暫時(shí)所得的結(jié)果（用于拼接最后結(jié)果）——實(shí)際上，這也是自底向上的算法的通病，無法像修剪枝條一樣砍掉其它部分。

b.利用備忘錄方法呢，就可以在遞歸處理問題的基礎(chǔ)上，將需要后來多次計(jì)算的問題進(jìn)行緩存，減少了重復(fù)子問題的計(jì)算。但是書中所記的備忘錄方法沒有真正的將自上而下的精髓體現(xiàn)出來，若是將自上而下的思想結(jié)合最優(yōu)子結(jié)構(gòu)的思想，則可以對(duì)問題進(jìn)行修剪枝條，在宏觀出即可去掉一大部分的不需計(jì)算的方面，比如一個(gè)問題的劃分可以有兩種，選擇了最優(yōu)的一種，就可以將另一種非最優(yōu)情況下的所有計(jì)算均省去，然后再對(duì)第一次的劃分再次進(jìn)行劃分，其結(jié)構(gòu)是樹由根向葉，不斷的擇取最優(yōu)的樹干，最終至葉子，非最優(yōu)樹干直接不計(jì)算。

最終效果圖

總結(jié)

以上是生活随笔為你收集整理的关于动态规划与备忘录方法的总结的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。