动态规划与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。
在用分治法求解时，有些子问题被重复计算了很多次。如果能够保存已解决的子问题的答案，在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式事件算法。为了达到这个目的，可以用一个表来记录所有已解决的子问题的答案，不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划的基本思想。

动态规划算法适用于解最优化问题。通常可以按以下步骤设计动态规划算法。
(1) 找出最优解的性质，并刻画其结构特征
(2) 递归地定义最优值
(3) 以自底向上的方式计算出最优值
(4) 根据计算最优值得到的信息，构造最优解
步骤(1)~(3)是动态规划算法的基本步骤

最长公共子序列

一个给定序列的子序列是在该序列中删去若干元素后得到的系列，确切地说，若给定序列X={x1,x2…xm}，则另一序列Z={z1,z2,…,zk}，X的子序列是指存在一个严格递增下标序列{i1,i2,i3….,ik}使得对于所有j=1,2……,k有zj = xij。例如：序列Z = {B,C,D,B}是序列X = {A,B,C,B,D,A,B}的子序列，相应的递增下标为: {2,3,5,7}
给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。
例如：
若X={A,B,C,B,D,A,B},Y={B,D,C,A,B,A}，序列{B,C,A}是X和Y的一个公共子序列。但它不是X和Y的最长公共子序列。
序列{B,C,B,A}也是X和Y的一个公共子序列，它的长度为4，而且它是X和Y的最长公共子序列，因为X和Y没有长度大于4的公共子序列。

思路：
序列X={x1,x2,x3,…,xm} 序列长度为m
序列Y={y1,y2,y3,…yn} 序列长度为 n
序列Z={z1,z2,z3,…zk} 序列长度为 k
① 当 m == 0 || n == 0时，则序列X和序列Y没有公共子序列。
② 如果m > 0 ， n > 0，且 xm == yn 时，这个时候，我们就可以缩小规模，
Zk-1 = Xm-1 && Yn-1
③ 如果m > 0，n > 0，且xm != yn时，我们分下面两种情况：
(1). xm != zk，则Zk = Xm-1 && Yn
(2). yn != zk，则Zk = Xm && Yn-1

我们定义定义 i 为 X序列的长度， j 为 Y序列的长度。
C(i,j) 表示 Z序列的长度。通过上面三种情况我们可以得到：

1.C(i,j) = 0 ，i==0 || j==0

2.C(i,j) = (C(i-1),(j-1)) +1， Xi==Yj 且 i>0 ,j >0 //这里加1是因为，在计算i-1和j-1这两个长度序列的公共子序列里时，我们只计算当前的公共子序列长度，而没有计算对于整个的最长公共子序列长度。所以需要加1。

3.C(i,j) = Max((C(i-1),j),C(i,(j-1))，Xi != Yj 且 i > 0, j > 0

代码实现：