线性dp之序列问题

线性dp之序列问题

【基本概念与性质】

1.子序列：一个序列 A＝a1,a2,……an 中任意删除若干项，剩余的序列叫做 A 的一个子序列。也可以认为是从序列 A 按原顺序保留任意若干项得到的序列。（例如：对序列｛1,3,5,4,2,6,8,7｝来说，序列｛3,4,8,7｝是它的一个子序列。）

2.公共子序列：如果序列 C 既是序列 A 的子序列，也是序列 B 的子序列，则称它为序列 A 和序列 B 的公共子序列。（例如：对序列｛1,3,5,4,2,6,8,7｝和序列｛1,4,8,6,7,5｝来说，序列｛1,8,7｝是它们的一个公共子序列）

3.最长公共子序列：A 和 B 的公共子序列中长度最长的（包含元素最多的）序列叫做 A 和 B 的公共子序列。（最长公共子序列不唯一）

4.对于一个长度为 n 的序列，它一共有 2^n 个子序列，有 (2^n – 1) 个非空子序列。

5.子序列不是子集，它和原始序列的元素顺序是相关的。

6.空序列是任何两个序列的公共子序列。

7.角标为 0 时，认为子序列是空序列。

【LIS问题】

LIS 问题（Longest Increasing Subsequence），最长上升子序列，其一般为求最长下降子序列或是最长上升子序列。用 DP[i] 表示 a[i] 为结尾的最长上升子序列的长度，则有状态转移方程: DP[i] = max(DP[i], DP[j]+1);

 1 int LIS(int a[], int n)
 2 {
 3     int DP[n];
 4     int Cnt=-1;
 5     memset(DP, 0, sizeof(DP));
 6     for(int i=0; i<n; i++ ){
 7         for(int j=0; j<i; j++ ){
 8             if( a[i]>a[j] ){
 9                 DP[i] = max(DP[i], DP[j]+1);
10                 Cnt = max(DP[i], Cnt);//记录最长序列所含元素的个数
11             }
12         }
13     }
14     return Cnt+1;//因为初始化为0,所以返回结果+1
15 }

【LCS 问题】

LCS问题（Longest Common Subsequence），求序列的最长公共子序列，M[i][j] 表示前缀子串 x[1~i] 与 y[1~j] 的最长公共子序列的长度，则有状态转移方程：M[i][j] = max(M[i-1][j]，M[i][j-1]，M[i-1][j-1]+1（if：x[i] = y[j]））

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 550;
 4 
 5 int main()
 6 {
 7     char x[maxn],y[maxn];
 8     int M[maxn][maxn], i, j;
 9     while( gets(x) && gets(y) ){
10         int len1 = strlen(x);
11         int len2 = strlen(y);
12         for( i=0; i<=len1; i++ ) M[i][0] = 0;
13         for( i=0; i<=len2; i++ ) M[0][i] = 0;
14         for( i=1; i<=len1; i++ ){
15             for( j=1; j<=len2; j++ ){
16                 if( x[i-1]==y[j-1] ){
17                     M[i][j] = M[i-1][j-1]+1;
18                 }
19                 else{
20                     M[i][j] = max(M[i-1][j],M[i][j-1]);
21                 }
22             }
23         }
24         printf("%d
", M[len1][len2]);
25     }
26     return 0;
27 }

【LCIS 问题】

LCIS 问题（Longest Common Increasing Subsequence），求序列的最长公共上升子序列。

dp[i][j] 表示 a[1]~a[i] 和 b[1]~b[j]并以b[j]结尾的最长公共上升子序列,如果a[i]不等于b[j]时，很明显dp[i][j]的值就等于dp[i-1][j]；如果a[i]等于b[j]时，就在b[1]~b[j]中寻找b[k]使得b[j]>b[k]而且dp[i][k]是最大的。即状态转移方程为：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn = 1111;
 5 
 6 int a[maxn],b[maxn],dp[maxn][maxn];
 7 int main()
 8 {
 9     int n,m;
10     scanf("%d%d",&n,&m);
11     for(int i=1;i<=n;i++){
12         scanf("%d",&a[i]);
13         dp[i][0] = 0;
14     }
15     for(int i=1;i<=m;i++){
16         scanf("%d",&b[i]);
17         dp[0][i]=0;
18     }
19     dp[0][0]=0;
20     int max1;
21     for(int i=1;i<=n;i++){
22         max1=0;//用来记录小于a[i]的b[j]中最大的dp[i][j];
23         for(int j=1;j<=m;j++){
24             if(a[i]!=b[j]){
25                 dp[i][j]=dp[i-1][j];
26             }
27             else{
28                 for(int k=1;k<j;k++){
29                     if( b[j]>b[k]){
30                         max1 = max(max1,dp[i][k]);
31                     }
32                 }
33                 dp[i][j]=max1+1;
34             }
35         }
36     }
37 
38 
39     int ans=0;
40     for(int i=1;i<=m;i++){
41         ans=max(ans,dp[n][i]);
42     }
43     printf("%d
",ans);
44 //    printf("%d
",dp[n][m]);
45     return 0;
46 }

View Code

以上程序的复杂度为O(n^3)，n太大的话就会超时。所以应该优化一下，当a[i] == b[j]时，才去遍历寻找max1，是在b[j]>b[k]的条件下，即在a[i]>b[k]所以可以先在[1,m]里面保存好max1的值，然后当a[i] == b[j]时，就可以直接令dp[i][j] = max1+1，时间复杂度就降为O(n^2)；因此对于决策集合中的元素只增多不减少的情景，就可以维护一个变量来记录决策集合的当前消息，只需要两重循环即可求解。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn = 1111;
 5 int a[maxn],b[maxn],dp[maxn][maxn];
 6 
 7 int main()
 8 {
 9     int n,m;
10     scanf("%d%d",&n,&m);
11     for(int i=1;i<=n;i++){
12         scanf("%d",&a[i]);
13         dp[i][0]=0;
14     }
15     for(int i=1;i<=m;i++){
16         scanf("%d",&b[i]);
17         dp[0][i]=0;
18     }
19     int max1;
20     dp[0][0]=0;
21     for(int i=1;i<=n;i++){
22         max1=0;
23         for(int j=1;j<=m;j++){
24             if( a[i]!=b[j] ){
25                 dp[i][j]=dp[i-1][j];
26             }
27             else{
28                 dp[i][j]=max1+1;
29             }
30             if( a[i]>b[j] && max1<dp[i][j]){
31                 max1 = dp[i][j];
32             }
33         }
34     }
35 
36     int ans=0;
37     for(int i=1;i<=m;i++){
38         ans=max(ans,dp[n][i]);
39     }
40     printf("%d
",ans);
41     return 0;
42 }

View Code

观察状态转移方程可以进行通过滚动数组压缩空间；即状态转移方程为：dp[j] = max(dp[k])+1(1<=k<j && b[j]>b[k])

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn = 1111;
 5 int a[maxn],b[maxn],dp[maxn];
 6 
 7 int main()
 8 {
 9     int n,m;
10     scanf("%d%d",&n,&m);
11     for(int i=1;i<=n;i++){
12         scanf("%d",&a[i]);
13     }
14     for(int i=1;i<=m;i++){
15         scanf("%d",&b[i]);
16         dp[i]=0;
17     }
18     int max1;
19     for(int i=1;i<=n;i++){
20         max1 = 0;
21         for(int j=1;j<=m;j++){
22             if( a[i]==b[j] ){
23                 dp[j]=max1+1;
24             }
25             if( a[i]>b[j] && max1<dp[j] ){
26                 max1 = dp[j];
27             }
28         }
29     }
30 
31     int ans=0;
32     for(int i=1;i<=m;i++){
33         ans=max(ans,dp[i]);
34     }
35     printf("%d
",ans);
36     return 0;
37 }