算法分析，備忘錄方法的遞歸方式是自頂向下的，動態(tài)規(guī)劃算法的遞歸方式是自底向上的，想問一下？Memo方法是動態(tài)規(guī)劃方法的一個變種。與動態(tài)規(guī)劃算法不同，memo方法的遞推方式是自頂向下的，而動態(tài)規(guī)劃算法是

算法分析，備忘錄方法的遞歸方式是自頂向下的，動態(tài)規(guī)劃算法的遞歸方式是自底向上的，想問一下？

Memo方法是動態(tài)規(guī)劃方法的一個變種。與動態(tài)規(guī)劃算法不同，memo方法的遞推方式是自頂向下的，而動態(tài)規(guī)劃算法是自下而上的。例如：LCS問題：當(dāng)席= YJ，C[I，J]只需要知道C[I-1，J-1 ]，而不是C[I，0 ]～C[I，J-1 ]和C[I-1，J]～C[I-1，N]。當(dāng)只需要一個LCS時，一些C[P，q]可能不會在整個溶液過程中使用。一般情況下，當(dāng)一個問題可以用動態(tài)規(guī)劃來求解時，二維數(shù)組中相當(dāng)數(shù)量的元素不會用到整個計算中。我們不需要遞歸地逐個計算二維數(shù)組中的元素。使用memo方法：數(shù)組中的元素只在需要計算時才計算，并且計算是遞歸的。計算完這些值后，將保存這些值以用于其他目的。例如：LCs的問題：首先，將C[I，0]（0≤I≤m）和C[0，J]（1≤J≤n）初始化為0。其余的m×nc[I，J]都初始化為-1。計算C[I，J]L2（x，y，I，J，C）的遞歸算法LCS（memo方法）：如果x[I]=y[J]，檢查C[I-1，J-1]，如果C[I-1，J-1]>-1（計算），將C[I-1，J-1]1賦值給C[I，J]，并返回。如果C[I-1，J-1]=-1（尚未計算），則遞歸調(diào)用LCS L2（x，y，I-1，J-1，C）計算C[I-1，J-1]，然后將C[I-1，J-1]1賦給C[I，J]，并返回。如果x[i]1，y[J]，檢查C[i-1，J]和C[i，J-1]。如果兩者都大于-1（已計算），則將Max{C[I-1，J]，C[I，J-1]}賦給C[I，J]，并返回。如果C[I-1，J]，C[I，J-1]中的一個等于-1（尚未計算），或者兩者都等于-1，則遞歸調(diào)用LCS，L2計算它，然后將Max{C[I-1，J]，C[I，J-1]}賦值給C[I，J]。如果大量的子問題不需要解決，memo方法可以節(jié)省時間。但是當(dāng)只需要計算少數(shù)或全部子問題時，遞歸方法比memo方法（如矩陣乘法、最優(yōu)二叉搜索樹）要好