[dynamic planning] counting garlic customers: the log of garlic King (the longest increasing public subsequence)

dp[i][j]: At the same time nums[i] The end and nums[j] Longest increasing common subsequence at the end

initialization ：

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

State transition equation ：

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

Time complexity 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;
	
}