刚才讲到了动态规划算法的递归实现。 动态规划算法递归实现的时候呢，由于同一个子问题 被多次地计算，所以它的时间复杂度呢比较高。 我们想的办法呢就是每个子问题只算一次，只算一次呢 后边用到的时候我们把那个值直接拿过来，这样就可以把时间降下来， 这个就是它的迭代实现。下面我们看一下 在迭代实现的时候，有一些关键问题需要来考虑。 第一个是每个子问题只算一次， 那你就需要注意这个迭代的过程，一定要从最小的子问题算起， 要把它的计算顺序明确下来，这样才能保证后边用到的值 前面已经算好了，存在那了。所以这个迭代的顺序是一个非常重要的，这个是迭代的起始， 下面是它的顺序。还需要考虑的就是用什么样的存储结构 来保留它的计算结果，中间每一步的子问题的计算结果 都留下来，这个就是它的备忘录，要考虑这个存储结构。 还要考虑它的解的追踪，当你这个 最后的优化函数算出来了以后，问题的解是什么？ 那是另外一件事情。我们优化函数，比如说矩阵链问题，它只是你的 这个运算次数，这个次数达到最小了，但是你到底括弧加在哪里？ 这个是问题的解，所以我们要通过这个 标记函数来标记每一步决策的位置，也就是加括弧运算的位置，这样才能找到它的解。因此 这个追踪解到底怎么个追踪，也需要把这个算法 想清楚。这是它的几个关键问题。 下面我们看一下矩阵链乘法的不同的这个子问题，到底我们 怎么来设计这个子问题的计算顺序，来保证这个迭代 后面用到的值前面已经算过了。那么长度，只含有1个矩阵， 这样的子问题，就是最小的子问题它有n个 子问题，这个不需要计算，因为它没有乘法。 长度是2，是2个矩阵的子问题，这有n-1个子问题。 长度是3的这样的矩阵有n-2个子问题， 一直到长度是n-1的，有两个子问题。长度是 n的，就是原始问题，只有一个，这是它的不同的子问题 有这么多个，根据它的规模我们把它列出来了。下边看一下迭代计算的顺序， 迭代计算的顺序呢，长度是1的，我们作为初值，都是0， 这个i 可以从1到n，就是m[1,1]到m[n,n]， 这是n个子问题。长度是2的是1到2的一个链，2到3的 链，一直到n-1到n的链，只有n-1个子问题。 长度是3的，1到3的，2到4的，一直到n-2到n的， 我们按照这样的顺序 从前到后每一行，每一行从左到右这样来计算。一直到长度是n-1 有两个子问题，先算第一个，再算第二个。最后这就是长度是n的，是原始问题。 这个是它的迭代计算的顺序，我们就按照这样的顺序来计算。 那么当你计算到后面的时候，可能会调用前面的子问题， 它的值直接拿过来就可以了。我们看看 具体的例子，这是n到8的这样的子问题，也就是说 一共是8个矩阵， 8个矩阵从A1到A8， 初值我们不考虑了。长度是2的， A1，A2，A2，A3到最后A7，A8， 这是它的子问题列出来了。长度是3的，一共是 6个子问题，列在这，这是它的计算顺序，从左到右。长度是4的， 长度是5的，是6的，是7的，最后是原始问题， 因为正好等于n了。这个是 子问题的计算顺序，我们就按照这样的顺序来做。下边看一下 矩阵链相乘算法的伪码，这个是迭代实现。 首先我们先赋初值，令所有的m[i,i]的 初值都为0，这就是长度是1的矩阵链。 然后我们对所有的链长进行迭代计算， 链长的最少的值是2，最长的值到n， 那么对于每一个给定的链长，我们在选择它的首边界 和后边界，所以这个地方是遍历所有长度是r的子问题， 那么从这个里头，它的计算就是具体对一个子问题的 计算，这一个子问题的计算呢一开始这几个步是矩阵链前边的 子问题指长度是1，只有1个矩阵，后边从i+1到j是后边 看作一个子问题，这样来做计算，这是第一步计算的结果。 然后这个分隔的位置k就开始移动，刚才那个分隔的位置 是划在i的后面，下面就从i+1到j-1， 陆续遍历所有可能的分隔的位置。 在这个分隔位置下，这是前一个矩阵的它的最少的乘法次数， 这是后边这个结果矩阵的最少的乘法次数，然后把这两个子问题的结果综合起来 需要做这么多的乘法次数，这就计算出来了在这个分隔位置下的 它的最少的次数，如果这个值比原来保存的值更小，这个时候 我们就要来做替换，所以遍历了所有的划分以后，就可以 通过这样的替换保留了最好的结果，就把这个解更新了。 这是我们看到的它的矩阵链相乘的 伪码。那么这里边有两个备忘录，s和m两个是备忘录， m记录的是最少在乘法次数所有子问题的最少的乘法次数， s呢是记录这个分界的位置，就是通过这样的 赋值来把这个分界位置记下来，这是它的伪码。 下面我们看一下时间复杂度。 时间复杂度的分析呢根据这个伪码，第二行是遍历所有可能的 链的长度，从2一直到n，所以这个是O(n)量级。第3行 它是确定子问题的首位置，这个首位置也有O(n)种选择的可能。那么当首位置定了以后， 链长定了，它的末位置也就定了，相当于把子问题定了。那么第7行呢，是对针对这个子问题 它要分隔成更小的子问题，这个k要移动，要进行切分， 那这个切分的量级也是O(n)，所以这三行的 它的循环都是O(n)的操作，那按照这个O(n)的 这样的一个操作有三个变量，那是n³种可能的子 内部操作，而内部操作呢是常数时间，所以它总的工作量是 O(n³)。那么另外一种估计工作量的方法就 根据备忘录来估计，因为备忘录里头每一项的工作量 一共对它的工作量再求和就可以了。而子问题一共 有多少个呢？就意味着这个备忘录有多少个项，一共有n²个 子问题，相当于它的每个矩阵链的前后边界 所有可能的组合，然后在每个子问题内部的工作量它 需要做划分，把它划分成更小的子问题，而这个 划分的次数大概是O(n)次。所以整个的 每一个子问题的工作量是O(n)，一共有n²个子问题， 也就是说它的备忘录有n²个项， 它的工作总时间是O(n³)，这个是关于它的这个时间的复杂度的估计。 那么追踪解的工作量是O(n)，把这两个工作量加到一起 当然它的总工作量还是O(n³)，这就是算法分析的结果。 看一个具体的例子，这是一个矩阵链， 这个矩阵链呢它的行列的参数给在这个p里面，这个是它的 矩阵个数，5个矩阵。那么对于它来讲， 它是这5个矩阵的行列号都可以由这个参数把它列出来， 它的备忘录刚好是所有子问题的 最小的乘法次数，还有划分位置来存储，这是备忘录的设计。 下边我们看一下一个具体的这个结果，就是刚才那个矩阵链。 在这儿，r=1是初值， 这个都赋成零。然后，我们 对链长是2的做计算，链长是2的， [1,2]一个子问题，[2,3]、[3,4]、[4,5]， 这是顺序计算，把这几个值算出来记在这个备忘录里面 然后，这是链长是3的，有3个子问题，这个是它的计算结果 这个是链长是4的两个子问题的计算结果，这是最后原始问题的最终结果 那么在这个计算中呢，我们看一个具体的步骤，比如说m[2,5]这个计算是怎么得到的。 m[2,5]的计算呢，它可能是这样的划分位置，就是第二个矩阵作为一个 子问题，[3,5]矩阵做一个子问题。那么这个值是0，这个值是2500 把它们俩合并的工作量应该是35,15和20。 好，应该这三个乘起来，也就是说这一项。 那这个0在这，这个2500在这项，加上合并的工作量 这是这一种划分的时候，它的最少的次数，那这个运算次数呢，我们可以观察到 它已经超过一万了。下边我们看到还有另外的划分位置， 那就是说，{2,3]作为前一个子问题， [4,5]作为第二个子问题。那么，这个第一个子问题的工作量2625，第二个工作量 1000，反应在这两项里头。然后，把这两个子问题合并，它是35,5,20， 这样的参数，所以就是合并的工作量在这一项里头，那这个算出来的结果呢是7125。- 啊，这是 第二个结果，比第一个结果要好。那还有 第三个划分的位置，就是[2,4]是一个子问题， 第五个矩阵自己是一个子问题，那这个结果是4375， 然后这个结果是0，这是初值，加上它们合并的工作量 35x10, 35,10,20，这个结果算出来也超过一万了。 所以，三个值最小的结果是这个7125，这就是 它的具体的计算过程。那么，我们在计算[2,5]的这个项的时候调用了前边的 刚才讲到的若干个值，啊，把它直接拿过来就可以了，这个就是备忘录。 然后我们看一下标记函数。标记函数呢， 它也是标记我们得到那个最优值的时候它的划分位置，那根据这个标记函数来 追踪最后的解，也就是加括弧加在哪里。我们由这个项来追踪，s[1,5]=3， 说明最后一次计算是在第三个矩阵后面作为划分位置计算的。 因此，我们就可以知道整个的计算最后一次是划在这个位置。 前三个矩阵的计算结果，后两个矩阵计算结果，然后把这两个作为最后的结果乘起来。 这是找到了这个位置，然后由它，我们还要追踪前面这个子问题，它究竟 乘法是按照什么顺序计算的，那就要查s[1,3]， s[1,3]呢是1，s[1,3]是1就说明 我们划分的位置在第一个矩阵后面，也就是说它是这样计算的 A2、A3算了，然后A1再和它来算，啊，这是它的计算。 那么把这个合到一起呢，我们就得到整个的计算顺序，A2、A3先算，A1再和它算。 把这个结果再和A4、A5的结果再算，就是这个最终的计算顺序，而它的 运算次数就是11875，就是刚才那个备忘录存的那个最少的乘法次数。 两种实现可以比较一下， 递归的实现复杂度高，空间比较小；迭代实现呢，时间复杂度 降低了，但是空间消耗加多了。原因呢，是因为递归实现 它是子问题多次重复计算，而子问题的计算次数有可能是指数量级的增长，而迭代计算呢， 每个子问题只算一次，所以这是它时间复杂度低的原因。 动态规划算法的时间复杂度 应该怎么估计呢，有两种办法。一个是通过备忘录各项来计算 它的工作量的总和，每一项工作量都加起来， 然后再和追踪解的工作量算，加到一起就可以了。 啊，可以通过这个办法来算，也可以通过递推方程来算。 啊，这两种办法都可以。一般来讲，这个追踪解的工作量比前边记录的 工作量一般地来讲要小，啊，所以常常很多问题的复杂度函数基本上就和 备忘录计算的工作量是一样的，这是它的递交。 最后，我们把这个算法的要素小结一下。划分子问题确定边界， 转换成多步判断的过程。定义优化函数， 以该函数的极大或极小来做依据，确定是不是满足优化原则。 列出优化函数的递推方程和边界条件。 自底向上的计算，也就是从最小的子问题算起，给定这个计算顺序。 然后设计这个备忘录，就是这个表格是什么样子来存储这个子问题的优化函数值和标记。 这个标记呢，有的问题需要设立，有的问题可能不需要设立， 所以要先想好要不要设立标记函数，标记函数的计算满足什么样的公式。 最后，它的复杂度估计可以用递推方程的方法 或者备忘录的方法来估计它的复杂度函数。
