线性动态规划——子序列问题
（有错误欢迎指出，部分解法灵感来源于洛谷题解）
文章目录
- 线性动态规划——子序列问题
-
- 1.最长上升子序列（LIS，Longest Increasing Subsequence）
-
- 1.1 解法（动态规划）
-
- 1.1.1 状态转移方程
- 1.1.2 时间复杂度
- 1.1.3 代码
- 1.2树状数组优化
-
- 1.2.1 思路
- 1.2.2 时间复杂度
- 1.2.3 具体操作
- 1.2.4 代码
- 2.其他子序列问题
-
- 2.1 最长不上升子序列
-
- 2.1.1 解法（动态规划）
-
- 2.1.1.1 状态转移方程
- 2.1.1.2 代码
- 2.1.2 树状数组优化
-
- 2.1.2.1 代码
- 2.2 最长公共子序列（LCS，Longest Common Subsequence）
-
- 2.2.1 解法（动态规划）
-
- 2.2.1.1 状态转移方程
- 2.2.1.2 时间复杂度
- 2.2.1.3 代码
- 2.2.2 树状数组优化（特定情况下可使用）
-
- 2.2.2.1 思路
- 2.2.2.2 具体操作
- 2.2.2.3 代码
- 3.总结
-
- 3.1 最长（非）上升/下降子序列问题
-
- 3.1.1 解法（动态规划）
- 3.1.2 树状数组优化
1.最长上升子序列（LIS，Longest Increasing Subsequence）
“给定n个整数 A 1 A_1 A1， A 2 A_2 A2， ⋯ \cdots ⋯， A n A_n An，按从左到右的顺序选出尽量多的整数，组成一个上升子序列（子序列可以理解为：删除0个或多个数，其他数的顺序不变）。例如序列1，6，2，3，7，5，可以选出上升子序列1，2，3，5，也可以选出1，6，7，但前者更长。选出的上升子序列相邻元素不能相等”——《算法竞赛入门经典》
1.1 解法（动态规划）
1.1.1 状态转移方程
d ( i ) = m a x { 0 , d ( j ) ∣ j < i , A [ j ] < A [ i ] } + 1 d(i)=max\{0, d(j)|j<i, A[j]<A[i]\}+1 d(i)=max{0,d(j)∣j<i,A[j]<A[i]}+1
1.1.2 时间复杂度
O ( n 2 ) O(n^2) O(n2)
1.1.3 代码
int LIS(){
for(int i=1;i<=n;i++){
for(int j=1;j<i;j++){
if(A[j]>A[i]) dp[i]=max(dp[i], dp[j])+1;
}
}
int ans=-1;
for(int i=1;i<=n;i++) ans=max(ans, dp[i]);
return ans;
}
1.2树状数组优化
1.2.1 思路
动态规划的状态转移方程 d ( i ) = m a x { 0 , d ( j ) ∣ j < i , A [ j ] < A [ i ] } d(i)=max\{0, d(j)|j<i, A[j]<A[i]\} d(i)=max{0,d(j)∣j<i,A[j]<A[i]}在计算第 i i i个元素是需要访问第 1 1 1至 i i i个元素，使时间复杂度为 O ( n 2 ) O(n^2) O(n2)。我们用树状数组优化这一步骤，就可以使时间复杂度降低。
1.2.2 时间复杂度
O ( n l o g n ) O(nlogn) O(nlogn)
1.2.3 具体操作
创建树状数组C，以A[i] i ∈ [ 1 , n ] _{i\in[1,n]} i∈[1,n]为C的下标，代表以A[i]为末尾的最长上升子序列的长度。
从1至n遍历A的元素，对于元素A[i]，用
qry1X()
求出以从1至A[i]为末尾的最长上升子序列的长度的最大值，对A[i]和大于A[i]的值更新为
k=qry1X()+1
（树状数组操作）。
k的最大值即为最长上升子序列的长度。
1.2.4 代码
int lowbit(int x) {return x&(-x);}
int qry1X(int x){
int ans=-1;
for(int i=x;i>0;i-=lowbit(i)){
ans=max(ans, C[i]);
}
return ans;
}
void chgXoo(int x, int k){
for(int i=x;i<=biggest;i+=lowbit(i)){ //biggest为A[i]的最大值
C[i]=max(C[i], k);
}
}
int d(){
memset(C, 0, sizeof(C));
int ans=-1;
for(int i=1;i<=cnt;i++){
int maxn=qry1X(A[i]);
chgXoo(A[i]+1, ++maxn); //因为单调上升，必须+1
ans=max(ans, maxn);
}
return ans;
}
2.其他子序列问题
2.1 最长不上升子序列
2.1.1 解法（动态规划）
2.1.1.1 状态转移方程
d ( i ) = m a x { 0 , d ( j ) ∣ j < i , A [ j ] > = A [ i ] } + 1 d(i)=max\{0, d(j)|j<i, A[j]>=A[i]\}+1 d(i)=max{0,d(j)∣j<i,A[j]>=A[i]}+1
时间复杂度和LIS相同
2.1.1.2 代码
int d(){
for(int i=1;i<=n;i++){
for(int j=1;j<i;j++){
if(A[j]>=A[i]) dp1[i]=max(dp[i], dp[j])+1;
}
}
int ans=-1;
for(int i=1;i<=n;i++) ans=max(ans, dp[i]);
return ans;
}
2.1.2 树状数组优化
2.1.2.1 代码
int lowbit(int x) {return x&(-x);}
int qryXoo(int x){
int ans=-1;
for(int i=x;i<=biggest;i+=lowbit(i)){
ans=max(ans, C[i]);
}
return ans;
}
void chg1X(int x, int k){
for(int i=x;i>0;i-=lowbit(i)){
C[i]=max(C[i], k);
}
}
int d(){
memset(C, 0, sizeof(C));
int ans=-1;
for(int i=1;i<=cnt;i++){
int maxn=qryXoo(A[i]);
chg1X(A[i], ++maxn);
ans=max(ans, maxn);
}
return ans;
}
2.2 最长公共子序列（LCS，Longest Common Subsequence）
2.2.1 解法（动态规划）
2.2.1.1 状态转移方程
d ( i , j ) = m a x { d ( i − 1 , j ) , d ( i , j − 1 ) } ( P [ i ] ≠ Q [ j ] ) d(i, j)=max\{d(i-1, j), d(i, j-1)\}(P[i]≠Q[j]) d(i,j)=max{d(i−1,j),d(i,j−1)}(P[i]=Q[j])
d ( i , j ) = m a x { d ( i − 1 , j ) , d ( i , j − 1 ) , d ( i − 1 , j − 1 ) + 1 } ( P [ i ] = Q [ j ] ) d(i, j)=max\{d(i-1, j), d(i, j-1), d(i-1, j-1)+1\}(P[i]=Q[j]) d(i,j)=max{d(i−1,j),d(i,j−1),d(i−1,j−1)+1}(P[i]=Q[j])
2.2.1.2 时间复杂度
O ( n 2 ) O(n^2) O(n2)
2.2.1.3 代码
int d(){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
dp[i][j]=max(dp[i-1][j], dp[i][j-1]);
if(P[i]==Q[j]) dp[i][j]=max(dp[i][j], dp[i-1][j-1]+1);
}
}
return dp[n][m];
}
2.2.2 树状数组优化（特定情况下可使用）
2.2.2.1 思路
引用自洛谷阮行止大佬的博客，原文中LIS和LCS有轻微混淆，提出如下修正
关于为什么可以转化成LIS问题，这里提供一个解释。
A: 3 2 1 4 5
B: 1 2 3 4 5
我们不妨给它们重新标个号：把3标成a,把2标成b，把1标成c……于是变成：
A: a b c d e
B: c b a d e
这样标号之后，LCS长度显然不会改变。但是出现了一个性质：
两个序列的子序列，一定是A的子序列。而A本身就是单调递增的。
因此这个子序列是单调递增的。
换句话说，只要这个子序列在B中单调递增，它就是A的子序列。
哪个最长呢？当然是B的LIS最长。
自此完成转化。
2.2.2.2 具体操作
按照P数组的数据对Q数组进行类似于离散化的操作
对Q数组求LIS
2.2.2.3 代码
洛谷P1439 【模板】最长公共子序列
int lowbit(int x){
return x&(-x);
}
int qry1X(int x){
int ans=-1;
for(int i=x;i>0;i-=lowbit(i)) ans=max(ans, C[i]);
return ans;
}
void chgXoo(int x, int k){
for(int i=x;i<=n;i+=lowbit(i)) C[i]=max(C[i], k);
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>P[i];
T[P[i]]=i;
}
for(int i=1;i<=n;i++){
int temp;
cin>>temp;
Q[i]=T[temp];
}
int ans=-1;
for(int i=1;i<=n;i++){
int maxn=qry1X(Q[i]);
chgXoo(Q[i], ++maxn);
ans=max(ans, maxn);
}
cout<<ans;
return 0;
}
3.总结
3.1 最长（非）上升/下降子序列问题
3.1.1 解法（动态规划）
最长上升（非下降）子序列
d ( i ) = m a x { 0 , d ( j ) ∣ j < i , A [ j ] < ( < = ) A [ i ] } + 1 d(i)=max\{0, d(j)|j<i, A[j]<(<=)A[i]\}+1 d(i)=max{0,d(j)∣j<i,A[j]<(<=)A[i]}+1
最长下降（非上升）子序列
d ( i ) = m a x { 0 , d ( j ) ∣ j < i , A [ j ] > ( > = ) A [ i ] } + 1 d(i)=max\{0, d(j)|j<i, A[j]>(>=)A[i]\}+1 d(i)=max{0,d(j)∣j<i,A[j]>(>=)A[i]}+1
3.1.2 树状数组优化
最长上升（非下降）子序列：搜索比A[i]小的数，更新大于（大于等于）A[i]的数
最长下降（非上升）子序列：搜索比A[i]大的数，更新小于（小于等于）A[i]的数
树状数组代码：
int lowbit(int x) {return x&(-x);}
void chg1X(int x, int k){
for(int i=x;i>0;i-=lowbit(i)){
C[i]=max(C[i], k);
}
}
int qry1X(int x){
int ans=-1;
for(int i=x;i>0;i-=lowbit(i)){
ans=max(ans, C[i]);
}
return ans;
}
void chgXoo(int x, int k){
for(int i=x;i<=biggest;i+=lowbit(i)){
C[i]=max(C[i], k);
}
}
int qryXoo(int x){
int ans=-1;
for(int i=x;i<=biggest;i+=lowbit(i)){
ans=max(ans, C[i]);
}
return ans;
}
![笔试面试题目：滑动窗口(二)[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)