我们先提出与"回路"有关的几个问题.

problem 1.1
试分析存在回路的状态空间对动态规划是否具有适用性.

problem 2.1
在一个无负回路的图中有两个节点 s, t, 试求两点间的第 k 短路径.

对于第一个问题, 我们将沿着半环上的动态规划继续走下去, 探讨一下非幂等半环上的动态规划问题, 从而给出动态规划的一个更为广义的适用范围; 对于后面一个问题, 我们将从 Dijkstra 算法的适用性谈起, 并分析几个典型的最短路径问题的算法, 最后给出一个普适的求前 k 短路径的算法和一个非常漂亮的 k 最优 Dijkstra 算法, 来完成这个问题的解答. 

动态规划针对特定问题求解的例子有很多, 本文将从普适的情况来系统地定义及分析动态规划. 我们首先提出两个问题. 

Problem 1.1
给定三个字符串A, B, C, 试求出 A 和 B 的一个满足下述条件的最长公共子序列: 这个子序列不能包含字符串 C 作为它的子序列. 

Problem 2.1
试分析动态规划问题的空间复杂度.

第一个问题是一个经典问题"最长公共子序列" (Longest Common Subsequence, LCS) 的一个扩展. 注意子序列 (subsequence) 和子串 (substring) 的区别在于, 子串指原字符串中连续出现的若干字符, 而子序列则不要求在原字符串中出现的字符连续 (保证次序即可). 举个例子, "hlo" 是字符串 "hello" 的子序列而不是子串, 因为它在 "hello" 中不连续.

第二个问题更系统一些. 仅仅用针对特殊动态规划问题的求解模型是回答不清楚这个问题的. 为了把它解释清楚, 我会从半环开始来定义动态规划问题的适用范围, 从而揭示出动态规划问题的本质, 并通过更底层的代数结构来解释动态规划的空间复杂度.

我们先提出一个问题.

Problem 1.1
有两个 n 行 n 列的矩阵 A, B. 定义两种运算, 第一种是计算 A 和 A 相乘的值, 第二种是计算 A 和 B 相乘的值. 求比较两种运算的复杂度.

即便我们不知道计算机是怎么实现矩阵乘法, 我们仍可以看到, 第一种运算是第二种运算的一个子问题, 因此复杂度不会高于后者. 

于是我们尝试计算一下矩阵的复杂度. 假定 A = [a[i][j]] 和 B = [b[i][j]] 的乘积是 C = [c[i][j]], 那么c[i][j]的值如下可求. 直观地讲, 计算出一个c[i][j]需要把 n 对 a[i][k] 和 b[k][j] 相乘, 因此需要至少 O(n) 的复杂度; 计算出整个 C 需要至少 O(n^3) 的复杂度.

事实上我们可以采用一些巧妙的办法对矩阵乘法进行提速. 而传统运算中也有一些很经典的提速算法, 最典型的是快速幂. 我们将介绍一下运算操作的原理和一些提速的方法, 进而剖析一下矩阵复杂度的问题, 进而分析problem 1.1中蕴含的奥秘.