动态规划法求解矩阵连乘问题 第三步：计算最优值 简单地递归计算m[1][n]将耗费指数时间 在递劃归计算时，许多子问题被重复计算多次 考虑1≤i≤j≤n的所有可能情况 不同的有序对(，)对应于不同的子问题 因此，不同子问题的个数最多只有： n(n-1)_n2-n 2 2 2 Φ 这也是该问题可用动态规划算法求解的又一显著特征 采用动态规划法，可依据其递归式以自底向上的方式进行计算 在计算过程中，保存已解决的子问题答案 每个子问题只计算一次，而在后面需要时只要简单查一下， 从而避免大量的重复计算，最终得到多项式时间的算法动态规划法求解矩阵连乘问题  第三步：计算最优值  简单地递归计算m[1][n]将耗费指数时间 • 在递归计算时，许多子问题被重复计算多次  考虑 1≤i≤j≤n 的所有可能情况 • 不同的有序对 (i, j) 对应于不同的子问题 • 因此，不同子问题的个数最多只有： 2 ( 1) 2 2 2   n n n n n − −   = =    这也是该问题可用动态规划算法求解的又一显著特征  采用动态规划法，可依据其递归式以自底向上的方式进行计算 • 在计算过程中，保存已解决的子问题答案 • 每个子问题只计算一次，而在后面需要时只要简单查一下， 从而避免大量的重复计算，最终得到多项式时间的算法