最长公共子序列, 最长递增子序列.

最长公共子序列(Longest Common Subsequence)

http://blog.csdn.net/hhygcy/archive/2009/03/02/3948969.aspx

问题描述:

注意这个问题是Subsequence不是Substring。substring的话就是子串，子串的要求的连续相等的字符序列，而subsequence不要求连续。比如说ABCD和ABD。他们的longest common subsequence就是ABD。而Longest common substring就是AB

DP算法:

我们把问题分成两种情况来讨论：

1. 如果S1[i] == S2[j]。就是i,j对应位置上的字符相等。那么可以得出M[i,j] = M[i-1,j-1]+1;为什么呢？可以想象的。如果M[i-1,j-1]也是一个最后方案，在这个最优方案上我们同时增加一个字符。而这两个字符又相等。那么我们只需要在这个M[i-1,j-1]的最优方案上++就可以了。

2. 如果S1[i] != S2[j]。那么就拿M[i-1,j]和M[i,j-1]来比较。M[i,j]的值就是M[i-1,j]和M[i,j-1]中大的值。这好比原来的字符串是S1[1...i-1]是ABC，S2[1...j-1]是ABE。那S1[1..i]是ABCE，S2[1..j]是ABEC。可以看出来这个时候 M[i,j]不是由M[i-1,j-1]决定的，而是由ABCE和ABE或者ABC和ABEC来决定的，也就是M[i-1,j]和M[i,j-1]。

所以我们可以把这个问题的递归式写成：

recursive formula

实现:

#include <stdio.h>
2

#include <assert.h>
3

#include <string.h>
4

template <typename T>
6

T max(T const & a, T const & b)
7

{
8

return a>b?a:b;
9

}
10

//最长公共子序列(Longest Common Subsequence)
12

int c[100][100];
13

int n1;
14

char x[100];
15

int n2;
16

char y[100];
17

//compute C[i][j]
19

int C( int i, int j)
20

{
21

if (i<0 || j<0)
22

return 0;
23

if(c[i][j]>=0)
25

return c[i][j];
26

if(x[i] == y[j])
28

c[i][j] = C(i-1, j-1) + 1;
29

else
30

c[i][j] = max(C(i, j-1), C(i-1, j));
31

return c[i][j];
33

}
34

void main()
36

{
37

for(int i=0; i<100*100;i++)
38

c[i/100][i%100] = -1;
39

printf("Input string 1:\n");
40

scanf("%s", x);
41

n1 = strlen(x);
42

printf("Input string 2:\n");
44

scanf("%s", y);
45

n2 = strlen(y);
46

printf("LCS is: %d", C(n1-1,n2-1));
48

printf("matrix c:\n");
50

for(int i=0; i<n1; i++)
51

{
52

for(int j=0; j<n2; j++)
53

printf("%d ", c[i][j]);
54

printf("\n");
55

}
56

}
57

最长递增子序列(Longest Increase Subsequence)

http://blog.csdn.net/hhygcy/archive/2009/03/02/3950158.aspx

问题描述:

这里subsequence表明了这样的子序列不要求是连续的。比如说有子序列{1, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 1, 7 }这样一个字符串的的最长递增子序列就是{1,3,4,5,6,7}或者{1,3,4,5,6,19}

方法1: 假设我们的初始的序列S1。那我们从小到大先排序一下。得到了S1'。这样我们再球 S1和S1'的最长公共子序列就可以知道答案了：）是不是有点巧妙啊

方法2 DP:

我们定义L(j)表示以第j个元素结尾的最长递增字串长度,是一个优化的子结构,也就是最长递增子序列.那么L(j)和L(1..j-1)的关系可以描述成

L(j) = max {L(i), i<j && Ai<Aj } + 1; 也就是说L(j)等于之前所有的L(i)中最大的的L(i)加一.这样的L(i)需要满足的条件就是Ai<Aj.这个推断还是比较容易理解的.就是选择j之前所有的满足小于当前数组的最大值.

//最长递增子序列(Longest Increase Subsequence)
2

#include <vector>
3

#include <iostream>
4

template <typename T>
6

T max(T const & a, T const & b)
7

{
8

return a>b?a:b;
9

}
10

//L(j) = max {L(i), i<j && Ai<Aj } + 1
12

//return the max LIS length
13

//output pos: start position of the LIS
14

int lis(int n, int const data[])
15

{
16

std::vector <int> L(n);
17

int maxLen = 0;
19

L[0] = 1;
20

for(int j=1; j<n; j++)
21

{
22

L[j]=1;
23

for(int i=0; i<j; i++)
24

{
25

if(data[i]<data[j])
26

L[j] = max(L[j], L[i]+1);
27

}
28

maxLen = max(maxLen, L[j]);
30

std::cout << j << " " << maxLen << std::endl;
32

}
33

return maxLen;
35

}
36

void main()
39

{
40

std::vector<int> data;
41

std::cout<<"Input data:\n";
42

int a;
43

while(std::cin>>a)
44

data.push_back(a);
45

int maxN = lis(data.size(), &data[0]);
47

std::cout<<maxN;
48

}
49

Published on Jun 29, 2009 in categories