【动态规划】计蒜客：蒜头君的日志（最长递增公共子序列）

dp[i][j]:同时以nums[i]结尾和nums[j]结尾的最长递增公共子序列

初始化：

dp[0][j]=0 dp[j][0]=0

状态转移方程：

nums[i]!=nums[j] dp[i][j]=0

nums[i]==nums[j]

dp[i][j]=max(dp[k][l])+1,nums[k]==nums[l] 0<=k<i ,0<=l<j

时间复杂度O(N^4)

#include<iostream>using namespace std;int n,m;int num1[4];int num2[3];int dp[4][3];void input(){cin>>n>>m;for(int i=1;i<=n;i++){cin>>num1[i];}for(int i=1;i<=m;i++){cin>>num2[i];}} int main(){int res=0;input();for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(num1[i]==num2[j]){for(int k=0;k<i;k++){for(int l=0;l<j;l++){if(num1[k]==num2[l])dp[i][j]=max(dp[i][j],dp[k][l]+1);res=max(res,dp[i][j]);}}}}}cout<<res;}