动态规划最长公共上升子序列问题

动态规划最长公共上升子序列问题（Longest Common Increasing Subsequence，简称 LCIS）是指给定两个序列 A 和 B，求它们的最长公共上升子序列的长度。其中，最长公共上升子序列指的是两个序列的子序列中，既是上升子序列，又是公共的最长子序列。

解决该问题的关键是设计状态转移方程。我们可以定义 dp[i][j] 表示 A[1...i] 和 B[1...j] 中以 B[j] 结尾的最长公共上升子序列的长度。状态转移方程如下：

1. 当 A[i] == B[j] 时，dp[i][j] = max{dp[k][m]} + 1，其中 k < i，m < j，A[k] < A[i]，B[m] < B[j]。

2. 当 A[i] != B[j] 时，dp[i][j] = dp[i][j-1]。

最终，我们需要遍历 dp 数组，找到所有 dp[i][j] 中的最大值，即为所求的最长公共上升子序列的长度。

时间复杂度为 O(n^2)，其中 n 为序列的长度。

相关问题

最长公共上升子序列代码

以下是最长公共上升子序列的代码实现（使用动态规划）：

def LCS(arr1, arr2):
    m, n = len(arr1), len(arr2)
    dp = [[0] * (n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if arr1[i-1] == arr2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

其中，`arr1`和`arr2`分别是两个需要比较的序列，`m`和`n`分别是它们的长度。`dp`是一个二维数组，表示最长公共上升子序列的长度。在每次遍历中，如果当前两个元素相等，则最长公共上升子序列长度加1；否则，取左边和上边的最大值作为当前最长公共上升子序列的长度。最后返回`dp[m][n]`即可。

最长公共上升子序列C++代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1005;
int n,m,a[maxn],b[maxn],f[maxn][maxn],pre[maxn][maxn];

int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=m;i++) scanf("%d",&b[i]);
for(int i=1;i<=n;i++){
int last=0;
for(int j=1;j<=m;j++){
f[i][j]=f[i-1][j];
pre[i][j]=pre[i-1][j];
if(a[i]==b[j]){
f[i][j]=f[last][j-1]+1;
pre[i][j]=last;
}
if(a[i]>b[j]&&f[i-1][j]>f[last][j-1]){
f[i][j]=f[i-1][j];
pre[i][j]=pre[i-1][j];
}
if(a[i]==b[j]) last=i;
}
}
int ans=0,pos=0;
for(int i=1;i<=n;i++){
if(f[i][m]>ans){
ans=f[i][m];
pos=i;
}
}
printf("%d\n",ans);
if(ans==0) return 0;
vector<int>res;
while(m){
res.push_back(a[pos]);
pos=pre[pos][m--];
}
for(int i=res.size()-1;i>=0;i--) printf("%d ",res[i]);
return 0;
}