矩阵连乘问题算法 算法分析，备忘录方法的递归方式是自顶向下的，动态规划算法的递归方式是自底向上的，想问一下？
算法分析，备忘录方法的递归方式是自顶向下的，动态规划算法的递归方式是自底向上的，想问一下？
Memo方法是动态规划方法的一个变种。与动态规划算法不同，memo方法的递推方式是自顶向下的，而动态规划算法是自下而上的。例如：LCS问题：当席= 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]可能不会在整个溶液过程中使用。一般情况下，当一个问题可以用动态规划来求解时，二维数组中相当数量的元素不会用到整个计算中。我们不需要递归地逐个计算二维数组中的元素。使用memo方法：数组中的元素只在需要计算时才计算，并且计算是递归的。计算完这些值后，将保存这些值以用于其他目的。例如：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（尚未计算），则递归调用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，则递归调用LCS，L2计算它，然后将Max{C[I-1，J]，C[I，J-1]}赋值给C[I，J]。如果大量的子问题不需要解决，memo方法可以节省时间。但是当只需要计算少数或全部子问题时，递归方法比memo方法（如矩阵乘法、最优二叉搜索树）要好
版权声明：本文内容由互联网用户自发贡献，本站不承担相关法律责任.如有侵权/违法内容,本站将立刻删除。
