（以下简称DP）
基本思想
将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。适合用DP求解的问题，经分解得到的子问题一般不是相互独立的，如果使用分治法求解，有些子问题会被重复计算多次，可以用一个表来记录所有已解决的子问题的答案，不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。
DP算法适用于解最优化问题。通常可以按以下步骤设计：
- 找出最优解的性质，并刻画其结构特征；
- 递归地定义最优值；
- 以自底向上的方式计算出最优值；
- 根据计算最优值时得到的信息，构造最优解
基本要素
最优子结构
问题的最优解包含了其子问题的最优解。重叠子问题
在用递归算法自顶向下求解问题时，每次产生的子问题并不总是新问题，有些子问题被计算多次。DP算法正式利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此问题时，只是简单地用常数时间查看一下结果。通常不同的子问题个数随问题的大小呈多项式增长，因此用DP算法通常只需要多项式时间，从而获得较高的解题效率。
最长公共子序列
问题描述
一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切的说，若给定序列X = {x1, x2, ..., xm}，则另一序列Z = {z1, z2, ..., zk}，X的子序列是指存在一个严格递增下标序列{i1, i2, ..., 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, ..., xm}和Y = {y1, y2, ..., ym}，找出X和Y的最长公共子序列。
按照DP算法设计的各个步骤求解
最长公共子序列结构
设序列X = {x1, x2, ..., xm}和Y = {y1, y2, ..., yn}的最长公共子序列为Z = {z1, z2, ..., zk}，则- 若
xm = yn，则zk = xm = yn，且Z
- 若
子问题的递归结构
- 计算最优值
- 构造最长公共子序列
- 算法的改进
