最长公共子序列, 最长递增子序列.
最长公共子序列(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]。
所以我们可以把这个问题的递归式写成:
实现:

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

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之前所有的满足小于当前数组的最大值.

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49
