备忘录的算法

Ⅰ 备忘录方法的而采用备忘录方法

：数组中的元素只是在需要计算时才去计算，
计算采用递归方式，值计算出来之后将其保存起来以备它用。
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]。
∴若有大量的子问题无需求解时，用备忘录方法较省时。
但当无需计算的子问题只有少部分或全部都要计算时，用递推方法比备忘录方法要好（如矩阵连乘，最优二分搜索树）