? 動態(tài)規(guī)劃算法的一個變形是備忘錄方法。備忘錄方法也用一個表格來保存已解決的子問題的答案，在下次需要解決此問題時，只要簡單地查看該子問題的解答，而不必重新計算。與動態(tài)規(guī)劃算法不同的是，備忘錄方法的遞歸方式是自頂向下的，而動態(tài)規(guī)劃算法則是自底向上遞歸的。因此，備忘錄方法的控制結(jié)構(gòu)與直接遞歸方法的控制結(jié)構(gòu)相同，區(qū)別在于備忘錄方法為每個解過的子問題建立了備忘錄以備需要時查看，避免了相同子問題的重復(fù)求解。

???? 備忘錄方法為每個子問題建立了一個記錄項，初始化時，該記錄項存入一個特殊的值，表示該子問題尚未求解。在求解過程中，對每個待求的子問題，首先查看相應(yīng)的記錄項。若記錄項中存儲的是初始化時存入的特殊值，則表示該子問題是第一次遇到，則此時計算出該子問題的解，并保存在相應(yīng)的記錄項中。若記錄項中存儲的已不是初始化時存入的特殊值，則表示該問題已被計算過，其相應(yīng)的記錄項中存儲的是該子問題的解答。此時，只要從記錄項中取出該子問題的解答即可。

?????? 一般來講，當(dāng)一個問題的所有子問題至少要解一次時，則用動態(tài)規(guī)劃算法比用備忘錄算法好。此時，動態(tài)規(guī)劃算法沒有任何多余的計算，還可利用其規(guī)則的表格存取方式，來減少在動態(tài)規(guī)劃算法中的計算時間和空間需求。當(dāng)子問題空間中部分子問題可不必求解時，用備忘錄方法則較有利，因為從其控制結(jié)構(gòu)可以看出，該方法只解那些確實需要求解的子問題。

總結(jié)

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

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