图6-13
最长公共子串的长度相同，都包含两个字母！但fosh与fish更像。
图6-14
这里比较的是最长公共子串，但其实应比较最长公共子序列：两个单词中都有的序列包含的
字母数。如何计算最长公共子序列呢？
图6-15
最终的网格如下。
图6-16
伪代码实现如下。
if (word_a[i] == word_b[j])
cell[i][j] = cell[i-1][j-1] 1;
else
cell[i][j] = max(cell[i-1][j], cell[i][j-1]);小结：
- 生物学家根据最长公共序列来确定DNA链的相似性，进而判断度两种动物或疾病有多相似。最长公共序列还被用来寻找多发性硬化症治疗方案。
- 你使用过诸如git diff等命令吗？它们指出两个文件的差异，也是使用动态规划实现的。
- 比较字符串的相似程度。编辑距离（levenshtein distance）指出了两个字符串的相似程度，也是使用动态规划计算得到的。编辑距离算法的用途很多，从拼写检查到判断用户上传的资料是否是盗版，都在其中。
- 你使用过诸如Microsoft Word等具有断字功能的应用程序吗？它们如何确定在什么地方断字以确保行长一致呢？使用动态规划！
动态规划对于解决多阶段决策问题的效果是明显的，但是动态规划也有一定的局限性。首先，它没有统一的处理方法，必须根据问题的各种性质并结合一定的技巧来处理；另外当变量的维数增大时，总的计算量及存贮量急剧增大。
动态规划的维数就是指状态变量的维数，而不是指决策变量或策略的维数。状态变量的维数过大，在应用动态规划的方法求解时将大大增加电子计算机的内存量。解题所需要的内存量一般按指数速度增加的。
因而，受计算机的存贮量及计算速度的限制，当今的计算机仍不能用动态规划方法来解决较大规模的问题，这就是“维数障碍”
八、附录附录1 证明最优子结构中原问题的最优解包含子问题的最优解以0-1背包问题为例证明。
0-1背包问题： 给定n中物品和一个背包，物品i的重量是wi,其价值为vi,背包的容量为C。如何选择装入背包的物品，使得装入背包中物品的总价值最大？
0-1背包问题等价于一个整数规划问题：
