備忘錄的演算法

Ⅰ 備忘錄方法的而採用備忘錄方法

：數組中的元素只是在需要計算時才去計算，
計算採用遞歸方式，值計算出來之後將其保存起來以備它用。
e.g. LCS問題：
首先將C[i,0](0≤i≤m)與C[0,j](1≤j≤n)初始化為0。
其餘m×n個C[i,j]全部初始化為-1。
計算C[i,j]的遞歸演算法LCS_L2(X,Y, i,j,C)（備忘錄方法）：
若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（尚未計算出來），
就遞歸調用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] ¹ y[j]，則要檢查C[i-1,j]和C[i,j-1]。

Ⅱ 演算法分析 備忘錄方法的遞歸方式是自頂向下的，動態規劃演算法的遞歸方式是自底向上的，想問一下，

備忘錄方法是動態規劃方法的變形。與動態規劃演算法不同的是，備忘錄方法的遞歸方式是自頂向下的，而動態規劃演算法則是自底向上的。
如： 求LCS的問題：
當xi=yj時，求C[i,j]只需知道C[i-1,j-1]，而無需用到C[i,0]～C[i,j-1]及C[i-1,j]～C[i-1,n]。
∴ 當只需求出一個LCS時，可能有一些C[p,q]在整個求解過程中都不會用到。
一般地，當某個問題可以用動態規劃法求解，但二維數組中有相當一部分元素在整個計算中都不會被用到。我們就不需要以遞推方式逐個計算二維數組中元素。
而採用備忘錄方法：數組中的元素只是在需要計算時才去計算，計算採用遞歸方式，值計算出來之後將其保存起來以備它用。
如：求LCS的問題：
首先將C[i,0](0≤i≤m)與C[0,j](1≤j≤n)初始化為0。其餘m×n個C[i,j]全部初始化為-1。
計算C[i,j]的遞歸演算法LCS_L2(X,Y, i,j,C)（備忘錄方法）：
若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（尚未計算出來），就遞歸調用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] ¹ 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，就遞歸調用LCS_L2將其計算出來，然後再把max{ C[i-1,j], C[i,j-1]} 賦給C[i,j]。
∴若有大量的子問題無需求解時，用備忘錄方法較省時。
但當無需計算的子問題只有少部分或全部都要計算時，用遞推方法比備忘錄方法要好（如矩陣連乘，最優二分搜索樹）