目录

动态规划的起源

概述

最优化问题

什么是最优化问题

例子——0/1背包问题

最优性原理

多阶段决策过程

最优性原理

动态规划方法的设计思想

动态规划方法适用条件

动态规划方法设计思路

动态规划与分治法的区别

动态规划方法的设计步骤

动态规划法的求解过程

两种求解方法

动态规划方法的关键

一个动态规划方法的实例——数塔问题

问题描述

问题分析

算法设计

算法分析

动态规划小结

图问题中的动态规划法

多段图的最短路径问题

问题描述

问题分析

求解过程

算法设计

算法分析

TSP问题

问题描述

问题分析

求解过程

算法设计

算法分析

算法实现—状态压缩之动态规划

组合问题中的动态规划法

最长递增子序列问题

问题描述

问题分析

求解过程

算法设计

算法分析

最长公共子序列问题（LCS）Longest Common Susequence

问题描述

问题分析

求解过程

算法设计

算法分析

0/1背包问题

问题描述

问题分析

算法设计

算法分析

查找问题中的动态规划法

最优二叉查找树

问题描述

问题分析

算法设计

近似串匹配问题

问题描述

问题分析

---

动态规划的起源

动态规划(dynamic programming) 是在20世纪50年代由美国数学家Richard Bellman为研究最优控制问题而提出的， programming的含义是计划和规划的意思，是运筹学的一个分支。

动态规划作为一种工具在应用数学中的价值被大家认同以后，在计算机科学界，动态规划法成为一种通用的算法设计技术来求解多阶段决策最优化问题。

 

概述

• 最优化问题

• 什么是最优化问题

最优化问题：有n个输入，它的解由这n个输入的一个子集组成，这个子集必须满足某些事先给定的条件，这些条件称为约束条件，满足约束条件的解称为问题的可行解。满足约束条件的可行解可能不只一个，为了衡量这些可行解的优劣，事先给出一定的标准，这些标准通常以函数的形式给出，这些标准函数称为目标函数，使目标函数取得极值（极大或极小）的可行解称为最优解，这类问题就称为最优化问题。       

• 例子——0/1背包问题

问题：给定n种物品和一个背包，物品i的重量是wi，其价值为vi，背包的容量为C。背包问题是如何选择装入背包的物品，使得装入背包中物品的总价值最大?

物品i只有两种选择xi ：装入背包xi =1或不装入背包xi =0

根据问题的要求，有如下约束条件和目标函数：

于是，问题归结为寻找一个满足约束条件（式1），并使目标函数（式2）达到最大的解向量X=(x1, x2, …, xn)。

 

• 最优性原理

• 多阶段决策过程

对于一个具有n个输入的最优化问题，其求解过程往往可以划分为若干个阶段，每一阶段的决策仅依赖于前一阶段的状态，由决策所采取的动作使状态发生转移，成为下一阶段决策的依据。从而，一个决策序列在不断变化的状态中产生。这个决策序列产生的过程称为多阶段决策过程。

因此，可以把每个阶段作为一个子问题处理，然后按照由小问题到大问题，以小问题的解支持大问题求解的方法，依次求解所有子问题并记录，最终得到原问题的解。

• 最优性原理

在多阶段决策过程的每一阶段，都可能有多种可供选择的决策，但必须从中选取一种决策。一旦各个阶段的决策选定之后，就构成了解决这一问题的一个决策序列，决策序列不同，所导致的问题的结果也不同。动态规划的目标就是要在所有容许选择的决策序列中选取一个会获得问题最优解的决策序列，即最优决策序列。

最优性原理（Optimal Principle）：过程的最优决策序列具有如下性质：无论决策过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的当前状态，构成一个最优决策序列。

如果一个问题满足最优性原理称此问题具有最优子结构性质。即各子问题的解只与它前面的子问题的解相关，而且各子问题的解都是相对于当前状态的最优解，整个问题的最优解是由各个子问题的最优解构成。这是可以使用动态规划法求解此问题的前提。

利用问题的最优子结构性质，动态规划法可以以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。

 

在每一阶段的决策中有一个赖以决策的策略或目标，这种策略或目标是由问题的性质和特点所确定，通常以函数的形式表示并具有递推关系，称为动态规划函数。

 

• 动态规划方法的设计思想

• 动态规划方法适用条件

能够分解为相互重叠（关联）的若干子问题；---多阶段决策过程

满足最优性原理（也称最优子结构性质：该问题的最优解中也包含着其子问题的最优解）。

• 动态规划方法设计思路

利用最优子结构性质，把原始问题划分成一系列子问题，每个子问题属于决策过程的一个阶段，然后以自底向上的方式递归地从子结构的最优解构造出原问题的最优解。

• 动态规划与分治法的区别

动态规划法和分治法的相同之处都是将待求解问题分解成若干个子问题，先求子问题的解，然后从这些子问题的解得到原问题的解。

动态规划算法与分治法的不同之处？

分治法要求子问题相互独立，否则重复求解，效率低下。

为了避免重复计算，动态规划方法对每个子问题仅求解一次，并将其结果保存在一个表中，以后用到时直接存取，不重复计算，节省计算时间。

 

例：计算斐波那契数：

n=5时分治法计算斐波那契数的过程。

分治法：代码在n=5时，fib(5)的计算过程如下:

fib(5)

fib(4) + fib(3)

(fib(3) + fib(2)) + (fib(2) + fib(1))

((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

(((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

由上面可以看出，分治法对于相似的子问题进行了重复的计算，因此不是一种高效的算法。实际上，该算法的运算时间是指数级增长的。

动态规划方法：由于计算F(n)是以计算它的两个重叠子问题 F(n-1)和F(n-2)的形式表达的，所以，可以设计一张表填入n+1个F(n)的值。

根据递推式计算所有元素，然后保存在数组中，这样在后面的计算中可以直接使用前面结果，从而避免了重复计算。显然，最后一项就是F(n)的值。动态规划法求解斐波那契数F(9)的填表过程 ：

动态规划的思想实质是分治思想和解决冗余

动态规划法求解问题通常采用自底向上的递推形式，但也可以采用自顶向下的形式(备忘录方法)。

 

• 动态规划方法的设计步骤

• 动态规划法的求解过程

(1)分段：第一步找到问题的“状态”(划分子问题)。将原问题分解为若干个子问题，每个子问题对应一个决策阶段，并且子问题之间具有重叠（关联）关系；

(2)分析：第二步找到“状态转移方程”(确定动态规划函数)。状态和状态之间关系式，称为状态转移方程。根据子问题之间的重叠关系找到子问题满足的递推关系式(即动态规划函数)。---动态规划法的关键；

(3)求解：第三步存储状态的值（填写表格），设计表格，利用递推式以自底向上的方式计算各个子问题的解并填表保存，实现动态规划过程。

  上述动态规划过程可以求得问题的最优值（即目标函数的极值），如果要求出具体的最优解，通常在动态规划过程中记录必要的信息，再根据计算最优值时得到的信息构造最优解。

1、分段（划分子问题）：找出最优解的性质，并刻划其结构特征。

2、分析（确定动态规划函数）：递归地定义最优值。

3、求解（填表）：以自底向上的方式计算出最优值。

4、根据计算最优值时得到的信息，构造最优解。

• 两种求解方法

（1）向前处理法：从最后阶段开始，以逐步向前递推的方式列出求前一阶段决策值的递推关系式，即根据xi+1,…,xn的那些最优决策序列来列出求取xi决策值的关系式，即：xi=f(xi+1,xi+2,…,xn)

（2）向后处理法：根据x1,…,xi-1的那些最优决策序列列出求xi的递推关系式。即：xi=f(x1,x2,…,xi-1)

• 动态规划方法的关键

关键在于获取各阶段间（子问题）的递推关系式---动态规划函数。

 

例子：斐波纳契数列F(n)

步骤1：划分子问题，用F（n）表示在斐波纳契数列中第n个数的值；

步骤2：动态规划函数（状态转移方程）：

步骤3：填表，以自底向上的方法来计算最优解

n	0	1	2	3	4	5	6	7	8	9	10
F(n)	1	1	2	3	5	8	13	21	34	55	89

步骤4：在数组中分析构造出问题的解；

 

• 一个动态规划方法的实例——数塔问题

• 问题描述

从数塔的顶层出发，在每一个结点可以选择向左走或向右走，一直走到最底层，要求找出一条路径，使得路径上的数值和最大。

此数塔的最大数值和是8+15+9+10+18=60

• 问题分析

观察发现，从5层数塔的顶层出发，下一层选择向左走还是向右走取决于两个4层数塔的最大数值和，显然，子问题具有重叠的特征。

如何找到子问题满足的动态规划函数？

动态规划的求解需要从底层开始进行决策，具体过程如下图所示

1、求解初始子问题：底层（第5层）的每个数字可以看作1层数塔，则最大数值和就是其自身；

2、再求解下一阶段的子问题：第4层的决策是在底层决策的基础上进行求解，可以看作4个2层数塔，对每个数塔进行求解；

3、再求解下一阶段的子问题：第3层的决策是在第4层决策的基础上进行求解，可以看作3个3层的数塔，对每个数塔进行求解；

以此类推，直到最后一个阶段：第1层的决策结果就是数塔问题的整体最优解。

数塔问题的存储结构

将数塔存储为下三角矩阵data[n][n]，二维数组maxAdd[n][n]存储动态规划每一步的决策结果，最后maxAdd[0][0]存储的就是数塔问题的最优解。

状态转移方程（动态规划函数）：      

求最大数值和的路径

设数组path[n][n]保存每一次决策所选择的数字在数组data[n][n]中的列下标，path[i][j]的值定义如下：    

• 算法设计

1.初始化数组maxAdd的最后一行为数塔的底层数据：

    for (j = 0; j < n; j++)

          maxAdd[n-1][j] = data[n-1][j];

2. 从第n-2层开始直到第 0 层对下三角元素maxAdd[i][j]执行下述操作：

   2.1maxAdd[i][j]=data[i][j]+

                              max{maxAdd[i+1][j], maxAdd[i+1][j+1]}；

   2.2 如果选择下标j的元素，则path[i][j] = j，

          否则path[i][j] = j+1；

3. 输出最大数值和maxAdd[0][0]；

4. 根据path数组确定每一层决策的列下标，输出路径信息；

• 算法分析

时间复杂性

–时间复杂性为：O(n^2)---因为i，j都有循环

空间复杂性

–需要空间O(n^2)

 

动态规划小结

一、动态规划解决问题的基本特征

二、动态规划方法适用条件

 

–满足最优性原理

–重叠子问题---多阶段决策过程

三、动态规划方法的关键---动态规划函数

图问题中的动态规划法

• 多段图的最短路径问题

• 问题描述

设图G=(V, E)是一个带权有向连通图，如果把顶点集合V划分成k个互不相交的子集Vi（2≤k≤n, 1≤i≤k），使得E中的任何一条边(u, v)，必有u∈Vi，v∈Vi+1（1≤i＜k），则称图G为多段图，称s∈V1为源点，t∈Vk为终点(汇点)。多段图的最短路径问题是求从源点s到终点t的最小代价路径。    

多段图最短路径——实例

W先生每天驾车去公司上班。W先生的住所位于A，公司位于F，图中的直线段代表公路，交叉点代表路口，直线段上的数字代表两路口之间的平均行驶时间。现在W先生的问题是要确定一条最省时的上班路线。

• 问题分析

由于多段图将顶点划分为k个互不相交的子集，所以，多段图划分为k段，每一段包含顶点的一个子集，每个子集中的顶点互不邻接。假设图中的顶点个数为n，则源点s的编号为0，终点t的编号为n-1，并且，对图中的任何一条边(u, v)，顶点u的编号小于顶点v的编号。

证明多段图问题满足最优性原理

设s, s1, s2, …, sp, t是从s到t的一条最短路径，从源点s开始，设从s到下一段的顶点s1已经求出，则问题转化为求从s1到t的最短路径，显然s1, s2, …, sp, t一定构成一条从s1到t的最短路径，如若不然，设s1, r1, r2, …, rq, t是一条从s1到t的最短路径，则s, s1, r1, r2, …, rq, t将是一条从s到t的路径且比s, s1, s2, …, sp, t的路径长度要短，从而导致矛盾。所以，多段图的最短路径问题满足最优性原理。

（用反证法）分析问题是否满足最优性原理：

1、先假设由问题的最优解导出的子问题的解不是最优的;

2、然后再证明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。

• 求解过程

第一步：划分子问题—找到问题状态

状态表示---利用向后处理法：xi=f(x1,x2,…,xi-1)

包含源s的子图都可以认为是一个子问题，子图的源是固定的，汇是可以变化的。子问题的数目等于图G中顶点的个数。

例如：要求d(0,9)，需要求解d(0,7) ，d(0,8) ，以此类推可以求得状态转移方程。当前状态应在前一个状态的基础上获得。

决策：采用利用向后处理法求最优值，最开始求解源s到第2段顶点集中每一个顶点的最短路径。这是最简单的子问题，最优值就等于边长。然后求解s到第3段顶点集中的每一个顶点的最优值，依此循环，直至求解s到t的最短路径值。

第二步：建立动态规划函数---状态转移方程

第三步：保存状态值---填表

用一个数组cost[n]作为存储最短路径长度的值（表格），cost[j]表示从源点s到顶点j的最短路径，数组path[n]存储状态转移，path[j]表示从源点s到顶点j的最短路径上，顶点j的前一个顶点。

• 算法设计

算法6.2：多段图的最短路径问题

输入：多段图的代价矩阵

输出：最短路径长度及路径

1. 循环变量j从1~n-1重复下述操作，执行填表工作：

    1.1 考察顶点j的所有入边，对于边(i, j)∈E：

        1.1.1  cost[j]=min{cost[i]+cij};

        1.1.2  path[j]=使cost[i]+cij最小的i;

    1.2  j++;

2. 输出最短路径长度cost[n-1];

3. 循环变量i=path[n-1]，循环直到path[i]=0：

    3.1 输出path[i];

    3.2  i=path[i];

• 算法分析

算法6.2主要由两部分组成：第一部分是依次计算从源点到各个顶点的最短路径，由两层嵌套的循环组成，外层循环执行n-1次，内层循环对所有入边进行计算，并且在所有循环中，每条入边只计算一次。假定图的边数为m，则这部分的时间性能是O(m)；第二部分是输出最短路径经过的顶点，设多段图划分为k段，其时间性能是O(k)。所以，算法6.2的时间复杂性为O(k+m)。

 

• TSP问题

• 问题描述

TSP问题是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求所走的路程最短。

各个城市间的距离可以用代价矩阵来表示。

• 问题分析

证明TSP问题满足最优性原理

设s, s1, s2, …, sp,s是从s出发的一条路径长度最短的简单回路，假设从s到下一个城市s1已经求出，则问题转化为求从s1到s的最短路径，显然s1, s2, …, sp, s一定构成一条从s1到s的最短路径。

如若不然，设s1, r1, r2, …, rq, s是一条从s1到s的最短路径且经过n-1个不同城市，则s, s1, r1, r2, …, rq, s将是一条从s出发的路径长度最短的简单回路且比s, s1, s2, …, sp, s要短，从而导致矛盾。所以，TSP问题满足最优性原理。

（用反证法）分析问题是否满足最优性原理：

1、先假设由问题的最优解导出的子问题的解不是最优的;

2、然后再证明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。

• 求解过程

第一步：划分子问题—找到“状态”

第二步：建立动态规划函数---状态转移方程

第三步：存储状态的值(填表)

假设n个顶点用0～n-1的数字编号，首先生成1～n-1个元素的子集存放在数组V[2n-1]中，设数组d[n][2n-1]存放迭代结果，其中d[i][j]表示从顶点i经过子集V[j]中的顶点一次且仅一次，最后回到出发点0的最短路径长度。

填表方法：自底向上，逐步求值。利用前一步求出的值计算后一步的值填入表中，每一步结束后选择最小值作为子问题的最优值，最后一步为原问题的最优解。

完成以下表格的填写：

j  i	{}	{1}	{2}	{3}	{1,2}	{1,3}	{2,3}	{1,2,3}
0								10
1	5		8	6			7
2	6	9		5		10
3	3	12	11		14
填表顺序	第1步	第2步			第3步			第4步

从顶点0出发的TSP问题的最短路径长度为10，路径是0→1→2→3→0。   

• 算法设计

设顶点之间的代价（邻接矩阵）存放在数组c[n][n]中，n个顶点用0～n-1的数字编号，首先生成1～n-1个元素的子集存放在数组V[2n-1]中，设数组d[n][2n-1]存放迭代结果，其中d[i][j]表示从顶点i经过子集V[j]中的顶点一次且仅一次，最后回到出发点0的最短路径长度。动态规划法算法如下：

算法——TSP问题

1．for (i=1; i<n; i++) d[i][0]=c[i][0];   //初始化第0列

2．for (j=1; j<2n-1-1; j++) 

         for (i=1; i<n; i++)   //依次进行第i次迭代

             if (子集V[j]中不包含i)

               对V[j]中的每个元素k，计算d[i][j]=min(c[i][k]+d[k][j-1]);

 3.  对V[2n-1-1]中的每一个元素k，

      计算d[0][2n-1-1]=min(c[0][k]+d[k][2^(n-1)-2]);

 4．输出最短路径长度d[0][2^(n-1)-1];

• 算法分析

显然，算法的时间和空间复杂度为O(2^n*n^2)。和蛮力法相比，动态规划法求解TSP问题，把原来的时间复杂性是O(n!)的排列问题，转化为组合问题，从而降低了算法的时间复杂性，但它仍需要指数时间。

• 算法实现—状态压缩之动态规划

状态压缩就是将一个阶段或（集合）的状态使用二进制0、1进行表示，这类问题中，状态只存在两种：有或无。通过二进制来达到节省存储空间和查找效率的作用。

为了更好理解状态压缩dp，首先介绍位运算相关的知识。

1.’&’符号，x&y，会将两个十进制数在二进制下进行与运算，然后返回其十进制下的值。例如3(11)&2(10)=2(10)。

2.’|’符号，x|y，会将两个十进制数在二进制下进行或运算，然后返回其十进制下的值。例如3(11)|2(10)=3(11)。

 

3.’^’符号，x^y，会将两个十进制数在二进制下进行异或运算，然后返回其十进制下的值。例如3(11)^2(10)=1(01)。

4.’<<’符号，左移操作，x<<2，将x在二进制下的每一位向左移动两位，最右边用0填充，x<<2相当于让x乘以4。相应的，’>>’是右移操作，x>>1相当于给x/2，去掉x二进制下的最右一位。

方法：x=x&(x-1)

以上四种运算在状态压缩dp中有着广泛的应用，常见的应用如下：

1.判断一个数字x二进制下第i位是不是等于1。

方法：if (((1<<(i-1))&x)>0)

将1左移i-1位，相当于制造了一个只有第i位上是1，其他位上都是0的二进制数。然后与x做与运算，如果结果>0，说明x第i位上是1，反之则是0。

2.将一个数字x二进制下第i位更改成1。

方法：x=x|(1<<(i-1))

证明方法与1类似，此处不再重复证明。

3.把一个数字二进制下最靠右的第一个1去掉。

方法：x=x&(x-1)

if(i!=0 &&(j&(1<<(i-1)))) continue;//i在j序列中出现，不需要求

if(d[i][j]==0) d[i][j]=c[i][k]+d[k][j-(1<<(k-1))];

else  d[i][j]=MIN(d[i][j], c[i][k]+d[k][j-(1<<(k-1))]);

理解：d[k][j-(1<<(k-1))]中， j-(1<<(k-1))表示在j的二进制串中，去掉k，因为由if( j&(1<<(k-1)))知道，k一定在j串中出现，例如：j=110,k=2,则j-(1<<(k-1))为100，所以d[k][j-(1<<(k-1))]表示从k出发，经过j中除去k以外的节点后回到起点城市的最短路径

 

组合问题中的动态规划法

• 最长递增子序列问题

• 问题描述

递增子序列：在数字序列A={a1, a2, …, an}中按递增下标序列(i1, i2,…, ik)（1≤i1< i2<…< ik≤n）顺序选出一个子序列B，如果子序列B中的数字都是严格递增的（注意：不要求连续），则子序列B称为序列A的递增子序列。

最长递增子序列：就是要找出序列A的一个最长的递增子序列。

例如：A={5, 2, 8, 6, 3, 6, 9, 7}

序列A的最长递增子序列的长度为4，有两个最长递增子序列，分别是{2, 3, 6, 9}和{2, 3, 6, 7})

• 问题分析

最优性原理：序列A={a1,a2,…,an}的最长递增子序列是B={b1,b2,…,bm}，首先证明最长递增子序列问题，满足最优性原理.
设序列A的最长递增子序列的第1个数字是b1，且b1=ai，则问题转换为求{ai,…,an} 的最长递增子序列，显然{b1,b2,…,bm} 一定是{ai,…,an} 的最长递增子序列，如若不然，设{b1,c2,…,ck}是序列{ai,…,an}的长度大于m的最长递增子序列，则{b1,c2,…,ck}将是序列{a1,a2,…,an}的长度大于m的最长递增子序列，从而导致矛盾。

• 求解过程

要解决这个问题，首先要定义这个问题和这个问题的子问题。但是从字面上看，找不出子问题

第一步：划分子问题

重新定义这个问题：

给定一个数列，长度为N，设L(i)为：以数列中第i项结尾的最长递增子序列的长度。求L(1), L(2), … ,L(i) 中的最大值。

显然，这个新问题与原问题等价。

而对于L(i)来讲， L(1), L(2), … ,L(i-1)都是L(i)的子问题：因为以第i项结尾的最长递增子序列（下称LIS），包含着以第1……i中某项结尾的LIS。

第二步：建立动态规划函数

分析原问题的解如何由子问题的解组合而成。

如果要求的这N个数的序列是：5，3，4，8，6，7

根据上面找到的状态，可以得到：

        前1个数的LIS长度L(1)=1 (序列：5)

        前2个数的LIS长度L (2)=1 (序列：3；3前面没有比3小的)

        前3个数的LIS长度L (3)=2 (序列：3，4；4前面有个比它小的3，所以L (3)=L(2)+1   )

        前4个数的LIS长度L(4)=3 ( 序列：3，4，8；8前面比它小的有3个数，所以 L(4) = max{L(1)+1, L(2)+1, L(3)+1}= 3 )

由此，动态规划函数已经很明显，如果已经求出了L(1)到L(i-1)， 那么L (i)可以得到下面的动态规划函数：

第三步：填表

测试数据：N个数的序列5，3，4，8，6，7

第三行表示前i个数中LIS的长度（最优值）， 第四行表示LIS中到达当前这个数的上一个数的下标，根据这个可以求出LIS序列（最优解） 

最长递增子序列问题——实例练习

序列A={5, 2, 8, 6, 3, 6, 9, 7}，写出求解过程并填表。

最长递增子序列问题——实例（填表）

序号i	1	2	3	4	5	6	7	8
序列元素a[i]	5	2	8	6	3	6	9	7
子序列长度L(i)	1	1	2	2	2	3	4	4
上一个数的下标	1	2	1	1	2	5	6	6
递增子序列	{5}	{2}	{5,8}, {2,8}	{5,6}, {2,6}	{2,3}	{2,3,6}	{2,3,6,9}	{2,3,6,7}

• 算法设计

数据结构：

设序列A存储在数组a[n]中

数组L[n]存储最长递增子序列的长度

其中L[i]表示元素序列a[0]~a[i]的最长递增子序列的长度

二维数组x[n][n]存储对应的最长递增子序列，其中x[i][n]存储a[0]~a[i]的最长递增子序列。

• 算法分析

设序列A的长度是n，算法依次对每一个序列元素进行计算，在求解L[i]时需要考察a[0]~a[i-1]是否小于a[i],因此，其时间复杂性为O(n^2)

 

• 最长公共子序列问题（LCS）Longest Common Susequence

• 问题描述

子序列

对给定序列X=(x1, x2,…, xm)和序列Z=(z1, z2,…, zk),Z是X的子序列当且仅当存在一个严格递增下标序列(i1, i2,…, ik),使得对于所有j=1, 2, …, k，有zj=xij（1≤ij≤m）。

公共子序列

给定两个序列X和Y，当另一个序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。

最长公共子序列问题

在序列X和Y的公共子序列中查找长度最长的公共子序列。

输入：X = (x1,x2,...,xn)，Y = (y1,y2,...ym)

输出：Z = X与Y的最长公共子序列

例如

X =(A，B，C，B，D，B，A)

Y =(B, D, C，A，B，A)

Z =(B, C, A)是X和Y的公共子序列

Z =(B, C, B，A)是X和Y的最长公共子序列

• 问题分析

证明LCS问题满足最优性原理

概念：

第i前缀:设X=(x1,x2,...,xn)是一个序列，X的第i前缀Xi是一个序列，定义为Xi=(x1,...,xi )

例. X=(A, B, D, C, A), X1=(A), X2=(A, B), X3=(A, B, D)

设序列X={x1, x2,…, xm}和Y={y1, y2,…, yn}的最长公共子序列为Z={z1, z2,…, zk}，Xk表示序列X中第k前缀，Yk表示序列Y中第k前缀，Zk表示序列Z中第k前缀，显然有下式成立：

（1）若xm=yn，则zk=xm=yn，且Zk-1是Xm-1和Yn-1的最长公共子序列；

（2）若xm≠yn且zk≠xm，则Z是Xm-1和Y的最长公共子序列；

（3）若xm≠yn且zk≠yn，则Z是X和Yn-1的最长公共子序列。

由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。 ---LCS问题满足最优性原理

• 求解过程

第一步：划分子问题

要找出序列X={x1, x2,…, xm}和Y={y1, y2,…, yn}的最长公共子序列，可按下述递推方式计算：

        当xm=yn时，找出Xm-1和Yn-1的最长公共子序列，然后在其尾部加上xm即可得到X和Y的最长公共子序列；

        当xm≠yn时，必须求解两个子问题：找出Xm-1和Y的最长公共子序列以及Xm和Yn-1的最长公共子序列，这两个公共子序列中的较长者即为X和Y的最长公共子序列。

X和Y的LCS的优化解结构为

LCSXY=LCSXm-1Yn-1+ <xm=yn>   if xm=yn

LCSXY=LCSXm-1Y                        if xm≠yn, zk≠xm

LCSXY=LCSXYn-1                         if  xm≠yn, zk≠yn

子问题重叠性

由于在所考虑的子问题空间中，总共有θ(mn)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。

第二步：建立动态规划函数

根据X和Y的LCS的优化解结构

LCSXY=LCSXm-1Yn-1+ <xm=yn>   if xm=yn

LCSXY=LCSXm-1Y                        if xm≠yn, zk≠xm

LCSXY=LCSXYn-1                         if  xm≠yn, zk≠yn

L[i, j] = Xi与Yj 的LCS的长度

LCS长度的动态规划函数

第三步：填表

基本思想：自底向上计算LCS的长度

计算过程

序列X={x1, x2,…, xm}和Y={y1, y2,…, yn}的最长公共子序列的求解过程可以分为m个阶段:

第1阶段，按照动态规划函数计算X1和Yj的最长公共子序列长度L[1][j]（1≤j≤n），第2阶段，按照动态规划函数计算X2和Yj的最长公共子序列长度L[2][j]（1≤j≤n），依此类推，最后在第m阶段，计算Xm和Yj的最长公共子序列长度L[m][j]（1≤j≤n），则L[m][n]就是序列Xm和Yn的最长公共子序列的长度。

• 算法设计

为了得到序列Xm和Yn具体的最长公共子序列，设二维表S[m+1][n+1]，其中S[i][j]表示在计算L[i][j]的过程中的搜索状态，并且有：

若S[i][j]=1，表明ai=bj，则下一个搜索方向是S[i-1][j-1]；

若S[i][j]=2，表明ai≠bj且L[i][j-1]≥L[i-1][j]，则下一个搜索方向是S[i][j-1]；

若S[i][j]=3，表明ai≠bj且L[i][j-1]＜L[i-1][j]，则下一个搜索方向是S[i-1][j]。

例：序列X=(a, b, c, b, d, b)，Y=(a, c, b, b, a, b, d, b, b)，建立两个(m+1)×(n+1)的二维表L和表S，分别存放搜索过程中得到的子序列的长度和状态。

• 算法分析

时间复杂性

–第一个for循环的时间性能是O(n)；

–第二个for循环的时间性能是O(m)；

–第三个循环是两层嵌套的for循环，其时间性能是O(m×n)；

–第四个for循环的时间性能是O(k)，而k≤min{m, n}；

–总时间复杂性为：O(mn)

空间复杂性

–使用数组L和B

需要空间O(mn)

 

• 0/1背包问题

• 问题描述

给定n种物品和一个背包，物品i的重量是wi，其价值为vi，背包的容量为C。背包问题是如何选择装入背包的物品，使得装入背包中物品的总价值最大?如果在选择装入背包的物品时，对每种物品i只有两种选择：装入背包或不装入背包，即不能将物品i装入背包多次，也不能只装入物品i的一部分，则称为0/1背包问题。

根据问题的要求，有如下约束条件和目标函数：

于是，问题归结为寻找一个满足约束条件式1，并使目标函数式2达到最大的解向量X=(x1, x2, …, xn)。

• 问题分析

证明0/1背包问题满足最优性原理

设(x1, x2, …, xn)是所给0/1背包问题的一个最优解，则( x2, …, xn)是下面一个子问题的最优解：

如若不然，设(y2, …, yn)是上述子问题的一个最优解，则

这说明(x1, y2, …, yn)是所给0/1背包问题比(x1, x2, …, xn)更优的解，从而导致矛盾。

第一步：划分子问题

设V(n, C)表示将n个物品装入容量为C的背包获得的最大价值，则由0/1背包问题的最优子结构性质，可以划分子问题。

子问题V(i，j)是背包容量为j，可选择物品为1,2,…,i时0/1背包问题的最优值。

0/1背包问题可以看作是决策一个序列(x1, x2, …, xn)，对任一变量xi的决策是决定xi=1还是xi=0。

初始子问题是把前面i个物品装入容量为0的背包和把0个物品装入容量为j的背包，得到的价值均为0，即：V(i, 0)= V(0, j)=0     （0≤i≤n, 0≤j≤C）

第二步：确定动态规划函数

考虑子问题，设V(i, j)表示将前i（1≤i≤n）个物品装入容量为j（1≤j≤C）的背包获得的最大价值，在决策xi时，已确定了(x1, …, xi-1)，问题处于下列两种状态之一：

（1）如果第i个物品的重量大于背包的容量，则装入前i个物品得到的最大价值和装入前i-1个物品得到的最大价值是相同的，即物品i不能装入背包；---xi=0

（2）如果第i个物品的重量小于背包容量，则会有以下两种情况：

        1）如果把第i个物品装入背包，则背包中物品的价值等于把前i-1个物品装入容量为j-wi的背包中的价值加上第i个物品的价值vi；

        2）如果第i个物品没有装入背包，则背包中物品的价值就等于把前i-1个物品装入容量为j的背包中所取得的价值。

显然，取二者中价值较大者作为把前i个物品装入容量为j的背包中的最优解。

令V(i, j)表示在前i(1≤i≤n)个物品中能够装入容量为j（1≤j≤C）的背包中物品的最大价值

动态规划函数：

第三步：填表

例如，有5个物品，其重量分别是{2, 2, 6, 5, 4}，价值分别为{6, 3, 5,4, 6}，背包的容量为10。

根据动态规划函数，用一个(n+1)×(C+1)的二维表V，V[i][j]表示把前i个物品(行号)装入容量为j（列号）的背包中获得的最大价值。

第四步：求最优解

填表顺序：第一阶段，只装入前1个物品，确定在各种情况下的背包能够得到的最大价值；第二阶段，只装入前2个物品，确定在各种情况下的背包能够得到的最大价值；依此类推，直到第n个阶段。最后，V(n,C)便是在容量为C的背包中装入n个物品时取得的最大价值。---一行一行填写。

求最优解：为了确定装入背包的具体物品，从V(n,C)的值向前推，如果V(n,C)>V(n-1,C)，表明第n个物品被装入背包，前n-1个物品被装入容量为C-wn的背包中；否则，第n个物品没有被装入背包，前n-1个物品被装入容量为C的背包中。依此类推，直到确定第1个物品是否被装入背包中为止。由此，得到如下函数：

• 算法设计

设n个物品的重量存储在数组w[n]中，价值存储在数组v[n]中，背包容量为C，数组V[n+1][C+1]存放迭代结果，其中V[i][j]表示前i个物品装入容量为j的背包中获得的最大价值，数组x[n]存储装入背包的物品，动态规划法求解0/1背包问题的算法如下：

• 算法分析

在算法中，第一个for循环的时间性能是O(n)，第二个for循环的时间性能是O(C)，第三个循环是两层嵌套的for循环，其时间性能是O(n×C)，第四个for循环的时间性能是O(n)，所以，算法的时间复杂性为O(n×C)。

 

查找问题中的动态规划法

• 最优二叉查找树

• 问题描述

设{r1, r2, …, rn}是n个记录的集合，其查找概率分别是{p1, p2, …, pn}，最优二叉查找树（Optimal Binary Search Trees）是以这n个记录构成的二叉查找树中具有最少平均比较次数的二叉查找树，即

最小，其中pi是记录ri的查找概率，ci是在二叉查找树中查找ri的比较次数。   

例如，集合{A, B, C, D}的查找概率是{0.1, 0.2, 0.4, 0.3}，

(a)的平均比较次数是0.1×1＋0.2×2+0.4×3+0.3×4=2.9，

(b)的平均比较次数是0.1×2＋0.2×1+0.4×2+0.3×3=2.1，

(c)的平均比较次数是0.1×3＋0.2×2+0.4×1+0.3×2=1.7。

• 问题分析

证明最优二叉查找树满足最优性原理

将由{r1, r2, …, rn}构成的二叉查找树记为T(1, n)，其中rk（1≤k≤n）是T(1, n)的根结点，则其左子树T(1, k-1)由{r1, …, rk-1}构成，其右子树T(k+1, n)由{rk+1, …, rn}构成。

若T(1, n)是最优二叉查找树，则其左子树T(1, k-1)和右子树T(k+1, n)也是最优二叉查找树，如若不然，假设T'(1, k-1)是比T(1, k-1)更优的二叉查找树，则T'(1, k-1)的平均比较次数小于T(1, k-1)的平均比较次数，从而由T'(1, k-1)、rk和T(k+1, n)构成的二叉查找树T'(1, n)的平均比较次数小于T(1, n)的平均比较次数，这与T(1, n)是最优二叉查找树的假设相矛盾。

设T(i, j)是由记录{ri, …, rj}(1≤i≤j≤n)构成的二叉查找树，C(i, j)是这棵二叉查找树的平均比较次数。虽然最后的结果是C(1, n)，但遵循动态规划法的求解方法,需要求出所有较小子问题C(i, j)的值，考虑从{ri, …, rj}中选择一个记录rk作为二叉查找树的根结点，可以得到如下关系：

因此，得到如下动态规划函数：

设一个二维表C[n+1][n+1]，其中C[i][j]表示二叉查找树T(i, j)的平均比较次数。注意到在式6.19中，当k=1时，求C[i][j]需要用到C[i][0]，当k=n时，求C[i][j]需要用到C[n+1][j]，所以，二维表C[n+1][n+1]行下标的范围为1～n+1，列下标的范围为0～n。

为了在求出由{r1, r2, …, rn}构成的二叉查找树的平均比较次数的同时得到最优二叉查找树，设一个二维表R[n+1][n+1]，其下标范围与二维表C相同，R[i][j]表示二叉查找树T(i, j)的根结点的序号。

例如，集合{A, B, C, D}的查找概率是{0.1, 0.2, 0.4, 0.3}，二维表C和R的初始情况如图6.13所示。

在二维表C和R中只需计算主对角线以上的元素。

首先计算C(1, 2)：

在前两个记录构成的最优二叉查找树的根结点的序号是2。

按对角线逐条计算每一个C(i, j)和R(i, j)，得到最终表。

• 算法设计

设n个字符的查找概率存储在数组p[n]中，动态规划法求解最优二叉查找树的算法如下：

 

• 近似串匹配问题

• 问题描述

设样本P=p1p2…pm，文本T=t1t2…tn，对于一个非负整数K，样本P在文本T中的K-近似匹配（K-approximate Match）是指P在T中包含至多K个差别的匹配（一般情况下，假设样本是正确的）。这里的差别是指下列三种情况之一：

（1）修改：P与T中对应字符不同；

（2）删去：T中含有一个未出现在P中的字符；

（3）插入：T中不含有出现在P中的一个字符。

 样本P和文本T为K-近似匹配包含两层含义：

（1）二者的差别数至多为K；

（2）差别数是指二者在所有匹配对应方式下的最小编辑错误总数。 

• 问题分析

证明近似串匹配问题满足最优性原理。

如果样本p1p2…pm在文本T的某一位置上有最优（差别数最小）的对应关系，则样本P的任意一个子串pi…pj（1≤i＜j≤m）与文本T的对应关系也必然是最优的。

动态规划函数：

定义一个代价函数D(i, j)(0≤i≤m,0≤j≤n)表示样本前缀子串p1…pi与文本前缀子串t1…tj之间的最小差别数，则D(m, n)表示样本P与文本T 的最小差别数。

根据近似匹配的定义，容易确定代价函数的初始值：

（1）D(0, j)=0，因为空样本与文本t1…tj有0处差别；

（2）D(i, 0)=i，因为样本p1…pi与空文本t1…tj有i 处差别。

当样本p1…pi与文本t1…tj对应时，D(i, j)有四种可能的情况：

（1）字符pi与tj相对应且pi=tj，则总差别数为D(i-1, j-1)；

（2）字符pi与tj相对应且pi≠tj，则总差别数为D(i-1, j-1)＋1；

（3）字符pi为多余，即字符pi对应于tj后的空格，则总差别数为D(i-1, j)＋1；

（4）字符tj为多余，即字符tj对应于pi后的空格，则总差别数为D(i, j-1)＋1。

例：已知样本P="happy"，K=1，T="Have a hsppy day"是一个可能有编辑错误的文本，在T中求1-近似匹配的过程如下：

由于D(5, 12)=1且m=5，所以，在t12处找到了差别数为1的近似匹配，此时的对应关系如下：

算法6.6的时间复杂性为O(m×n)。 ​​​​​​​