I have understood and implements lcs but unable to approach k-ordered lcs question. Can you please tell me how should I approach this question ?
K-ordered lcs : 2D DP
I have implemented the same way, but it’s giving me TLE.
Code : import java.util.*; public class k_lcs { static int dp[][][]; static int a[]; static int b[]; static int n,m; static int solve(int i,int j,int k) { if(i==n || j==m) return 0; if(dp[i][j][k]!=0) return dp[i][j][k]; int res = 0; if(a[i]==b[j]) return 1 + solve(i+1,j+1,k); if(k>0) res = 1 + solve(i+1,j+1,k-1); res = Math.max(res,solve(i,j+1,k)); res = Math.max(res,solve(i+1,j,k)); return dp[i][j][k]=res; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); int k = sc.nextInt(); dp = new int[n+1][m+1][k+1]; a = new int[n]; b = new int[m]; int i,j,p; for(i=0;i<n;i++) a[i] = sc.nextInt(); for(j=0;j<m;j++) b[j] = sc.nextInt(); System.out.println(solve(0,0,k)); } }