什么是动态规划

递归可以通过不断分解问题，将复杂的任务简化为最基本的小问题，比如基于递归实现的归并排序、排列和组合。不过有时候，我们不用处理所有可能的情况，只要找到满足条件的最优解就行了。这种情况下，我们需要在各种可能的局部解中，找出那些可能达到最优的局部解，而放弃其他的局部解。这个寻找最优解的过程其实就是动态规划。

通过不断分解问题，可以将任务简化为最基本的小问题。我们需要在各种可能的局部解中，找出可能达到最优的局部解。这个寻找最优解的过程就是动态规划。

动态规划的关键

动态规划特别注重子问题之间的转移关系。我们把子问题之间的转移称为状态转移，并把用于刻画这些状态转移的表达式称为状态转移方程。找到合适的状态转移方程，就是动态规划的关键。

求状态转移方程

当搜索引擎 的搜索模框中输入单词的时候，搜索引擎会返回一系列相关的关键词，方便你直接点击。甚至，当你某个单词输入有误的时候，搜索引擎依旧会返回正确的搜索结果，这两个功能就是查询推荐。测量拉丁文相似度，最常用的指标是编辑距离。

空null m o u s e
空null 0 1 2 3 4 5
m 1 min(2,2,0)=0 min(3,1,2)=1 min(4,2,3)=2 min(5,3,4)=3 min(6,4,5)=4
o 2 min(1,3,2)=1 min(2,2,0)=0 min(3,1,2)=1 min(4,2,3)=2 min(5,3,4)=3
u 3 min(2,4,3)=2 min(1,3,2)=1 min(2,2,0)=0 min(3,1,2)=1 min(4,2,3)=2
u 4 min(3,5,4)=3 min(2,4,3)=2 min(1,3,1)=1 min(2,2,1)=1 min(3,2,2)=2
s 5 min(4,6,5)=4 min(3,5,4)=3 min(2,4,3)=2 min(2,3,1)=1 min(3,2,2)=2
e 6 min(5,7,6)=5 min(4,6,5)=4 min(3,5,4)=3 min(2,4,3)=2 min(3,3,1)=1

我们假设字符数组A[]和B[]分别表示字符串A和B，A[i]表示字符串A中的第i个位置的字符，B[i]表示字符串B中第i个位置字符。
有了这些定义，我们就可以用迭代来表达上述的推导过程