Lecture 8: Dynamic Programming

Ordering Matrix Multiplications

Example: 计算矩阵乘法

两个矩阵相乘的运算时间

Problem: 以何种计算顺序时计算时间最少

Exhaustive seaerch

令为计算（记为）的方法数量。首先将一分为二。
那么就可以得到关于b的递推式：

hint: 对于每一种分割只需将两边的计算方法相乘即可

最终得到：

Recurrence equations

令时计算的最优时间消耗，那么有递推式