首先是lis的状态划分图
然后是lcs
结合lis和lcs两种dp问题的分析方法，我们就可以得出lcis的状态分析图
1.首先上升子序列的分析方法：以某个数字为结尾
2.其次公共子序列的分析方法：有4种状态 00，01，10，11
！！！双关键字的问题一般都以“消元”掉某个关键字来进行降维处理
状态表示
集合：所有以a[1,i]和b[1,j]构成的且以b[j]为结尾的公共上升子序列
属性：max
不包含a[i]:那么这个集合的最大值=dp[i-1][j]
包含a[i]:在包含a[i]时，我们发现它有多种状态子集，需要进一步划分
由于需要上升子序列，所以要对集合中的各个元素进行遍历
因为所有以b[k]结尾的公共上升子序列的最大值一定是dp[i][k](简单可证)
所以我们枚举 Σ(1~j)max(dp[i][j],dp[i-1][k]+1)
子序列只包含b[j]一个数，长度是1；
子序列的倒数第二个数是b[1]的集合，最大长度是f[i - 1][1] + 1；
…
子序列的倒数第二个数是b[j - 1]的集合，最大长度是f[i - 1][j - 1] + 1；
dp[i-1][k]是i-1的原因为：定义出发,dp[i][k]是考虑了a[1,i]和b[1,k]，dp[i-1][k]是考虑了a[1,i-1]和b[1,k]
如果采用dp[i][k]会导致a[i]被重复计算了两次，可能b[k]==b[j]
决策集合：dp[i][j]的决策集合，所有以a[1..i-1]和b[1,k]元素构成，且以b[k]结尾的公共上升子序列集合
#include <iostream>
#include <algorithm>
using namespace std;
const int N=3000+5;
int a[N];
int b[N];
int dp[N][N];
int t[N];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
cin>>b[i];
int res=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
dp[i][j]=dp[i-1][j]; //比较包含a[i]和不包含哪个更好
if(a[i]==b[j])
{
for(int k=0;k<j;k++)
if(b[k]<b[j])
dp[i][j]=max(dp[i-1][k]+1,dp[i][j]);
}
}
}
for(int i=1;i<=n;i++)
res=max(res,dp[n][i]);
cout<<res;
}1.寻找重复操作
2.寻找性质优化
重复操作：在第三重循环时，我们在寻找以b[j]结尾的lcis时，会有重复操作
寻找以b[j]为结尾时，我们需要遍历一遍前面1~j-1 所有元素
寻找以b[j+1]为结尾时，我们需要遍历一遍前面1~j 所有元素
我们可以注意到 b1~bj-1这一段元素是可以不用再次遍历的，存在重复操作。
对于决策集合来说，遍历到j+1，j进入，集合中的元素只增加不减少
那么引用前缀和的思想，引入一个前缀最大值来维护前面的最长公共上升子序列长度
寻找性质优化：
我们注意到一个值被放入决策集合中时，都是在b[j]==a[j]这个大前提条件下的
if(a[i]==b[j])
{
for(int k=0;k<j;k++)
if(b[k]<b[j]) //这里也可以写成b[k]<a[i] 因为a[i]==b[j]
dp[i][j]=max(dp[i-1][k]+1,dp[i][j]);
}
在第二重循环1~j时，i是固定的，即a[i]也是固定的
由于一个子序列能够放入集合中条件a[i]>b[k],那么我们可以在第二重循环中维护一个前缀最大值
for(int i=1;i<=n;i++)
{//maxv表示前缀最大值(前面最长的公共上升子序列+1)
int maxv=1; //最差情况是本身
for(int j=1;j<=n;j++)
{
dp[i][j]=dp[i-1][j];
if(a[i]==b[j]) //a[i]是公共子序列，更新值
dp[i][j]=max(dp[i][j],maxv);
//b[j]被放入j+1的决策集合中，检查
if(a[i]>b[j]) //a[i]>b[k] 才表示可以放入
maxv=max(maxv,dp[i-1][j]+1);
}
}问题：
1.为什么可以用a[i]>b[j]代替
我们要求的是最长公共上升子序列
假设a[i]==b[j]，第二重循环时，a[i]会逐渐和1~j-1中所有元素进行比较，如果a[i]>b[k](k表示此时的j)，那么等价于b[j]>b[k],如果不存在这个b[j]，循环结束后，dp[i][...]都是0，如果存在这个b[j]，那么维护的这个前缀最大值可以派上用场
2.为什么maxv和dp[i-1][j]取max，而不是f[i][j]
和dp[i-1][j]取max是继承上一步On^3的思路，f[i][j]表示a[i]已经和b[j]匹配过了，我们maxv维护的是所有包含a[i]且以b[j]为结尾的子序列最大长度,应该是a[i]还没有匹配过。
应是dp[i-1][j]+1 //1表示ai被匹配，
换成dp[i][j]和maxv能过是因为
如果b[j]==b[j+1]，他们不是上升的子序列，不会被重复计数，取max时可以重复，但是思路是错误的，如果取不严格上升子序列，用f[i][j]会出错
#include <iostream>
#include <algorithm>
using namespace std;
const int N=3000+5;
int a[N];
int b[N];
int dp[N][N];
int t[N];
int g[N][N]; //一个决策集合
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
cin>>b[i];
int res=0;
for(int i=1;i<=n;i++)
{//maxv表示前缀最大值(前面最长的公共上升子序列+1)
int maxv=1; //最差情况是本身
for(int j=1;j<=n;j++)
{
dp[i][j]=dp[i-1][j];
if(a[i]==b[j]) //a[i]是公共子序列，更新值
dp[i][j]=max(dp[i][j],maxv);
//b[j]被放入j+1的决策集合中，检查
if(a[i]>b[j]) //a[i]>b[k] 才表示可以放入
maxv=max(maxv,dp[i-1][j]+1);
}
}
for(int i=1;i<=n;i++)
res=max(res,dp[n][i]);
cout<<res;
}实现转移方程时，要注意观察决策集合的范围随着状态的变化情况，对于决策集合元素只 增加不减少 的情况，可以像本题一样维护一个变量来记录决策集合的当前信息，避免重复扫描，达到降维的作用