转:http://blog.csdn.net/yysdsyl/article/details/4226630
动态规划法
经常会遇到复杂问题不能简单地分解成几个子问题,而会分解出一系列的子问题。简单地采用把大问题分解成子问题,并综合子问题的解导出大问题的解的方法,问题求解耗时会按问题规模呈幂级数增加。
为了节约重复求相同子问题的时间,引入一个数组,不管它们是否对最终解有用,把所有子问题的解存于该数组中,这就是动态规划法所采用的基本方法。
【问题】 求两字符序列的最长公共字符子序列
问题描述:字符序列的子序列是指从给定字符序列中随意地(不一定连续)去掉若干个字符(可能一个也不去掉)后所形成的字符序列。令给定的字符序列X=“x0,x1,…,xm-1”,序列Y=“y0,y1,…,yk-1”是X的子序列,存在X的一个严格递增下标序列<i0,i1,…,ik-1>,使得对所有的j=0,1,…,k-1,有xij=yj。例如,X=“ABCBDAB”,Y=“BCDB”是X的一个子序列。
考虑最长公共子序列问题如何分解成子问题,设A=“a0,a1,…,am-1”,B=“b0,b1,…,bm-1”,并Z=“z0,z1,…,zk-1”为它们的最长公共子序列。不难证明有以下性质:
(1) 如果am-1=bn-1,则zk-1=am-1=bn-1,且“z0,z1,…,zk-2”是“a0,a1,…,am-2”和“b0,b1,…,bn-2”的一个最长公共子序列;
(2) 如果am-1!=bn-1,则若zk-1!=am-1,蕴涵“z0,z1,…,zk-1”是“a0,a1,…,am-2”和“b0,b1,…,bn-1”的一个最长公共子序列;
(3) 如果am-1!=bn-1,则若zk-1!=bn-1,蕴涵“z0,z1,…,zk-1”是“a0,a1,…,am-1”和“b0,b1,…,bn-2”的一个最长公共子序列。
这样,在找A和B的公共子序列时,如有am-1=bn-1,则进一步解决一个子问题,找“a0,a1,…,am-2”和“b0,b1,…,bm-2”的一个最长公共子序列;如果am-1!=bn-1,则要解决两个子问题,找出“a0,a1,…,am-2”和“b0,b1,…,bn-1”的一个最长公共子序列和找出“a0,a1,…,am-1”和“b0,b1,…,bn-2”的一个最长公共子序列,再取两者中较长者作为A和B的最长公共子序列。
求解:
引进一个二维数组c[][],用c[i][j]记录X[i]与Y[j] 的LCS 的长度,b[i][j]记录c[i][j]是通过哪一个子问题的值求得的,以决定搜索的方向。
我们是自底向上进行递推计算,那么在计算c[i,j]之前,c[i-1][j-1],c[i-1][j]与c[i][j-1]均已计算出来。此时我们根据X[i] = Y[j]还是X[i] != Y[j],就可以计算出c[i][j]。
问题的递归式写成:
回溯输出最长公共子序列过程:
算法分析:
由于每次调用至少向上或向左(或向上向左同时)移动一步,故最多调用(m + n)次就会遇到i = 0或j = 0的情况,此时开始返回。返回时与递归调用时方向相反,步数相同,故算法时间复杂度为Θ(m + n)。
代码:
#include <stdio.h>
#include <string.h>
#define MAXLEN 100
void LCSLength(char *x, char *y, int m, int n, int c[][MAXLEN], int b[][MAXLEN])
{
int i, j;
for(i = 0; i <= m; i++)
c[i][0] = 0;
for(j = 1; j <= n; j++)
c[0][j] = 0;
for(i = 1; i<= m; i++)
{
for(j = 1; j <= n; j++)
{
if(x[i-1] == y[j-1])
{
c[i][j] = c[i-1][j-1] + 1;
b[i][j] = 0;
}
else if(c[i-1][j] >= c[i][j-1])
{
c[i][j] = c[i-1][j];
b[i][j] = 1;
}
else
{
c[i][j] = c[i][j-1];
b[i][j] = -1;
}
}
}
}
void PrintLCS(int b[][MAXLEN], char *x, int i, int j)
{
if(i == 0 || j == 0)
return;
if(b[i][j] == 0)
{
PrintLCS(b, x, i-1, j-1);
printf("%c ", x[i-1]);
}
else if(b[i][j] == 1)
PrintLCS(b, x, i-1, j);
else
PrintLCS(b, x, i, j-1);
}
int main(int argc, char **argv)
{
char x[MAXLEN] = {"ABCBDAB"};
char y[MAXLEN] = {"BDCABA"};
int b[MAXLEN][MAXLEN];
int c[MAXLEN][MAXLEN];
int m, n;
m = strlen(x);
n = strlen(y);
LCSLength(x, y, m, n, c, b);
PrintLCS(b, x, m, n);
return 0;
相关推荐
运用动态规划算法解决最长公共子序列问题,计算最长公共子序列长度的动态规划算法LCS_LENGTH(X,Y)以序列X=, x2, …, xm>和Y=, y2, …, yn>作为输入。输出两个数组c[0..m ,0..n]和b[1..m ,1..n]。其中c[i,j]存储Xi与...
1. 要求按动态规划法原理求解问题; 2. 两个序列数据通过键盘输入; 3. 要求显示结果。
最长公共子序列问题就是给定两个序列X={x1,x2,...xm}和Y={y1,y2,...yn},找出X和Y的一个最长公共子序列。 Input 输入包含多组测试数据。第一行为一个整数C,表示有C组测试数据,接下来有C行数据,每组测试数据...
程序以输出正确的结果大家不要费心去修改,用c++编写
求X和Y的最长公共子序列长度以及最长公共子序列 2 对于给定的字符串A和字符串B,编程计算其编辑距离d(A,B)。 随机产生20以上的字符,放入输入文件input.txt,如:X={A,B,C,B,D,A,B}和Y={B,D,C,A,B,A}。 程序运行结束...
【问题描述】使用动态规划算法解最长公共子序列问题,具体来说就是,依据其递归式自底向上的方式依次计算得到每个子问题的最优值。 【输入形式】在屏幕上输入两个序列X和Y,序列各元素数间都以一个空格分隔。 ...
最长公共子序列,动态规划算法可有效地解此问题。下面我们按照动态规划算法设计的各个步骤来设计一个解此问题的有效算法
最长公共子序列(Longest Common Subsequence,LCS)问题是一个经典的动态规划问题,通常用于比较两个序列的相似程度。给定两个序列,找出它们之间的最长公共子序列的长度。 下面是一个 Python 的动态规划实现: `...
求两个字符串序列的最长公共子序列,利用动态规划求出最优解。
最长公共子序列问题 最长公共子序列问题(Longest Common Subsequence,LCS)是计算机科学和生物信息学中的一个经典问题。这个问题是寻找两个(或多个)给定序列的最长子序列,这个子序列在两个序列中都以相同的相对...
动态规划思想的介绍(矩阵连乘问题,最长公共子序列,流水线作业调度问题,0-1背包问题)。算法课使用的ppt,可结合我的博客算法专栏一起看。有详细代码。
注意这里是连续的子串。算法导论的动态规划部分讲了字符串最长公共子串的解法,但是那个子串是可以不连续的
最长公共子序列python实现,最长公共子序列是动态规划基本题目,下面按照动态规划基本步骤解出来。 1.找出最优解的性质,并刻划其结构特征 序列a共有m个元素,序列b共有n个元素,如果a[m-1]==b[n-1],那么a[:m]和b[:...
LCS问题具有最优子结构和重叠子问题的性质,因此采用动态规划算法自底向上计算该问题的解,并输出求到的LCS。用C程序实现。
解最长公共子序列问题时最容易想到的算法是穷举搜索法,即对X的每一个子序列,检查它是否也是Y的子序列,从而确定它是否为X和Y的公共子序列,并且在检查过程中选出最长的公共子序列。X的所有子序列都检查过后即可求...
动态规划适用于多种实际应用场景,例如最短路径问题、背包问题、字符串匹配问题、最长公共子序列问题以及最长递增子序列问题等。在实际应用中,动态规划可以大大提高算法的性能,并找到问题的最优解。 总的来说,...
动态规划通常用于解决最优化问题,比如最短路径、最长公共子序列、背包问题等。 动态规划的基本思想是将原问题分解为若干个子问题,先求解子问题的最优解,然后根据子问题的最优解递推得到原问题的最优解。为了避免...
它通常用于解决最优化问题,如最长公共子序列、最短路径等。动态规划的核心思想是将问题分解成重叠子问题,并使用记忆化搜索或自底向上的方法来避免重复计算。通过建立状态转移方程,动态规划可以高效地求解问题,...
学习要点: 理解动态规划算法的概念。 掌握动态规划算法的基本要素 (1)最优子结构性质 (2)重叠子问题性质 ...(2)最长公共子序列; (3)最大子段和 (4)凸多边形最优三角剖分; (5)背包问题;
动态规划 动态规划(Dynamic Programming,简称DP)是一种在数学、计算机科学和经济学中使用的,通过把原问题分解为相对简单的子问题的方式来求解复杂问题的方法。...5. **序列问题**:如最长递增子序列、最长公共子