关于动态规划求两字符序列的最长公共字符子序列的问题
传说这是标题党什么是动态规划？
百度定义是：动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著Dynamic Programming，这是该领域的第一本著作。
其实远没有那么复杂，简单的说就是求最优解，一个复杂的问题下分解出来的若干小型问题的所有解，放入某个固定的数组，不用每次递归求解。这就是基本方法
给个实例：
问题描述：字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列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和B，称序列Z是A和B的公共子序列，是指Z同是A和B的子序列。问题要求已知两序列A和B的最长公共子序列。
题目看着很复杂，其实很简单，大多数的题目都是靠这种晕人眼睛卖迷糊我们，我们细细分析下就可以知道如何下手了
如采用列举A的所有子序列，并一一检查其是否又是B的子序列，并随时记录所发现的子序列，最终求出最长公共子序列。这种方法因耗时太多而不可取，所以我们需要引入一个2维数组，对所有解进行逆推。这里给出教科书通用的证明方式：
设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[j]为序列“a0，a1，…，ai-2”和“b0，b1，…，bj-1”的最长公共子序列的长度
（1）c[j]=0
如果i=0或j=0；
（2）c[j]= c[i-1][j-1]+1
如果I，j>0，且a[i-1]=b[j-1]；
（3）c[j]=max（c[j-1]，c[i-1][j]） 如果I，j>0，且a[i-1]!=b[j-1]。
有个相应的数学公式我们就可以顺利堆出代码
下面给出权威的算法导论的源码[code]#include <iostream>
using namespace std;
const int m = 7; //序列X长度
const int n = 6; //序列Y长度
int c[8][7]; //存储Xi和Yi的一个LCS长度
char b[8][7]; //用来简化最优解的构造
void LCSLength(int m, int n, char *x, char *y) //计算LCS的长度
{
int i, j;
for(i = 1; i <= m; i)
{
c[i][0] = 0;
}
for(i = 1; i <= n; i)
{
c[0][i] = 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] = '\\';
}
else if(c[i-1][j] >= c[i][j-1])
{
c[i][j] = c[i-1][j];
b[i][j] = '|';
}
else
{
c[i][j] = c[i][j-1];
b[i][j] = '-';
}
}
}
}
void PrintLCS(int i, int j, char *x) //构造一个LCS
{
if(i == 0 || j == 0)
return;
if(b[i][j] == '\\')
{
PrintLCS(i - 1, j - 1, x);
cout<< x[i-1] << endl; //
}
else if(b[i][j] == '|')
{
PrintLCS(i - 1, j, x);
}
else
{
PrintLCS(i, j - 1, x);
}
}
void main()
{
char x[m] = { 'a' , 'b' , 'c' , 'b' , 'd' , 'a' , 'b' }; //表X
char y[n] = { 'b' , 'd' , 'c' , 'a' , 'b' , 'a' }; //表Y
LCSLength(m , n , x , y);
PrintLCS(m , n , x);
}[/code] 留个题目大家思考
Human Gene Functions
It is well known that a human gene can be considered as a sequence, consisting of four nucleotides, which are simply denoted by four letters, A, C, G, and T. Biologists have been interested in identifying human genes and determining their functions, because these can be used to diagnose human diseases and to design new drugs for them.
A human gene can be identified through a series of time-consuming biological experiments, often with the help of computer programs. Once a sequence of a gene is obtained, the next job is to determine its function. One of the methods for biologists to use in determining the function of a new gene sequence that they have just identified is to search a database with the new gene as a query. The database to be searched stores many gene sequences and their functions �C many researchers have been submitting their genes and functions to the database and the database is freely accessible through the Internet.
A database search will return a list of gene sequences from the database that are similar to the query gene. Biologists assume that sequence similarity often implies functional similarity. So, the function of the new gene might be one of the functions that the genes from the list have. To exactly determine which one is the right one another series of biological experiments will be needed.
Your job is to make a program that compares two genes and determines their similarity as explained below. Your program may be used as a part of the database search if you can provide an efficient one.
Given two genes AGTGATG and GTTAG, how similar are they? One of the methods to measure the similarity of two genes is called alignment. In an alignment, spaces are inserted, if necessary, in appropriate positions of the genes to make them equally long and score the resulting genes according to a scoring matrix.
For example, one space is inserted into AGTGATG to result in AGTGAT-G, and three spaces are inserted into GTTAG to result in �CGT--TAG. A space is denoted by a minus sign (-). The two genes are now of equal length. These two strings are aligned:
AGTGAT-G
-GT--TAG
In this alignment, there are four matches, namely, G in the second position, T in the third, T in the sixth, and G in the eighth. Each pair of aligned characters is assigned a score according to the following scoring matrix.
* denotes that a space-space match is not allowed. The score of the alignment above is (-3)+5+5+(-2)+(-3)+5+(-3)+5=9.
Of course, many other alignments are possible. One is shown below (a different number of spaces are inserted into different positions):
AGTGATG
-GTTA-G
This alignment gives a score of (-3)+5+5+(-2)+5+(-1) +5=14. So, this one is better than the previous one. As a matter of fact, this one is optimal since no other alignment can have a higher score. So, it is said that the similarity of the two genes is 14.
Input
The input consists of T test cases. The number of test cases ) (T is given in the first line of the input. Each test case consists of two lines: each line contains an integer, the length of a gene, followed by a gene sequence. The length of each gene sequence is at least one and does not exceed 100.
Output
The output should print the similarity of each test case, one per line.
Sample Input
2
7 AGTGATG
5 GTTAG
7 AGCTATT
9 AGCTTTAAA
Output for the Sample Input
14
21
页:
[1]