首页 > 代码库 > ·DP」知识点整理

·DP」知识点整理

2024-07-02 22:28:49   225人阅读

 

一.最长公共子序列（LCS Longest Common  Subsequence）

 

第一，先说区别，最长公共子串和最长公共子序列是不一样的。
最长公共子串不许是连续的，而最长公共子序列可以是不联系的。

网络上解释的子序列:
一个字符串S，去掉零个或者多个元素所剩下的子串称为S的子序列。最长公共子序列就是寻找两个给定序列的子序列，该子序列在两个序列中以相同的顺序出现，但是不必要是连续的。
例如
X=ABCBDAB
Y=BDCABA
BCA是X和Y的一个公共子序列，但是不是X和Y的最长公共子序列，
BCBA是X和Y的一个LCS，序列BDAB也是。


寻找LCS的一种方法是枚举X所有的子序列，然后注意检查是否是Y的子序列，并随时记录发现的最长子序列。

第二，子序列和子串的个数：
假设X有m个元素，则X有2^m-1个子序列
子串的话应该有（1+2+3+...+m） = (m+1)*m/2个


第三，可以参考一个blog：http://www.ahathinking.com/archives/115.html
DP最终处理的还是数值（极值做最优解），找到了最优值，就找到了最优方案；

为了找到最长的LCS，我们定义dp[i][j]记录序列LCS的长度，合法状态的初始值为当序列X的长度为0或Y的长度为0，公共子序列LCS长度为0，即dp[i][j]=0，所以用i和j分别表示　序列X的长度和序列Y的长度，状态转移方程为

dp[i][j] = 0  如果i=0或j=0
dp[i][j] = dp[i-1][j-1] + 1  如果X[i-1] = Y[i-1]
dp[i][j] = max{ dp[i-1][j], dp[i][j-1] }  如果X[i-1] != Y[i-1]

 

模板1

 1 #include<cstdio>
 2 #include<cstring>
 3 
 4 using namespace std;
 5 #define CLR(a,b) memset(a,b,sizeof(a))
 6 #define MAXN 1000
 7 short dir[MAXN][MAXN];
 8 int dp[MAXN][MAXN];
 9 
10 char A[MAXN], B[MAXN];
11 int r,c;
12 
13 void LCS()
14 {
15     for(int i=0;i<=r;i++)
16         dp[i][0] = 0;
17     for(int i=0;i<=c;i++)
18         dp[0][i] = 0;
19     for(int i=1;i<=r;i++)
20     {
21         for(int j=1;j<=c;j++)
22         {
23             if(A[i-1] == B[j-1])
24             {
25                 dp[i][j] = dp[i-1][j-1] + 1;
26                 dir[i][j] = 1;
27             }
28             else if(dp[i-1][j] >= dp[i][j-1])
29             {
30                 dp[i][j] = dp[i-1][j];
31                 dir[i][j] = 0;
32             }
33             else
34             {
35                 dp[i][j] = dp[i][j-1];
36                 dir[i][j] = 2;
37             }
38         }
39     }
40 }
41 
42 void print(int ri,int ci)
43 {
44     if(ri == 0 || ci == 0)
45         return;
46     if(dir[ri][ci] == 1)
47     {
48         print(ri-1,ci-1);
49         printf("%c",A[ri-1]);
50     }
51     else if(dir[ri][ci] == 0)
52         print(ri-1,ci);
53     else
54         print(ri,ci-1);
55 }
56 
57 
58 
59 int main()
60 {
61     scanf("%s%s",A,B);
62     r = strlen(A), c= strlen(B);
63     LCS();
64     printf("%d\n",dp[r][c]);
65     print(r,c);
66     printf("\n");
67     return 0;
68 }
View Code

模板2(滚动数组)

 1 /*************************************************
 2 Copyright:   Call_Me_BIGBALLON    
 3 Author:      BIGBALLON
 4 Problem:     111 - History Grading
 5 Date:        2014-05-04  
 6 Description: 
 7 **************************************************/
 8 #include<cstdio>
 9 #include<cstring>
10 #include<algorithm>
11 
12 using namespace std;
13 
14 int dp[2][21];
15 int A[21];
16 int B[21];
17 int r, c, k, t, len;
18 
19 void LCS()
20 {
21     for(int i=0;i<r;i++)
22         dp[i][0] = 0;
23     for(int i=0;i<c;i++)
24         dp[0][i] = 0;
25         
26     for(int i=1;i<=r;i++)
27     {
28         t = i & 1;
29         for(int j=1;j<=c;j++)
30         {
31             if(A[i] == B[j])
32                 dp[t][j] = dp[t^1][j-1] + 1;
33             else
34                 dp[t][j] = max(dp[t][j-1],dp[t^1][j]);
35         }
36     }
37 }
38 
39 int main()
40 {
41     scanf("%d",&len);
42     for(int i=1;i<=len;i++)
43         scanf("%d",&k), A[k] = i;
44         
45     while(scanf("%d",&k)!=EOF)
46     {
47         B[k] = 1;
48         for(int i=2;i<=len;i++)
49             scanf("%d",&k), B[k] = i;
50         r = c = len;
51         LCS();
52         printf("%d\n",dp[t][c]);
53     }
54     
55 }
View Code

 


联系
我们