3d array in k - ordered lcs

#1

Hello everyone :smile: I didn’t get how we used the 3D array for memoization in the k ordered LCS problem of the dynamic programming section

#2

dp[i][j] [k]

for any string between i …j we are storing the optimal answer for different values of K.
K = 0, 1,2,3,4,5… K = 3 means we have worked on string between i to j and we used 3 replacements.

1 Like
#3

import java.util.*;
public class Main {
static int dp[][][]=new int[220][220][220];
public static void main(String args[]) {
Scanner sc=new Scanner(System.in);
String str1=sc.next();
String str2=sc.next();
String str3=sc.next();
int m=str1.length();
int n=str2.length();
int o=str3.length();
System.out.println(lcs(str1,str2,str3,m,n,o));
}
public static int lcs(String str1,String str2,String str3,int m,int n,int o){
if(m==0 || n==0 || o==0){
return 0;
}
String ros1=str1.substring(1);
String ros2=str2.substring(1);
String ros3=str3.substring(1);
if(dp[m-1][n-1][o-1]!=0){
return dp[m-1][n-1][o-1];
}
if(str1.charAt(0)==str2.charAt(0) && str2.charAt(0)==str3.charAt(0)){
dp[m-1][n-1][o-1]=1+lcs(ros1,ros2,ros3,m-1,n-1,o-1);
return dp[m-1][n-1][o-1];
}
else{
int f1=lcs(ros1,str2,str3,m-1,n,o);
int f2=lcs(str1,ros2,str3,m,n-1,o);
int f3=lcs(str1,str2,ros3,m,n,o-1);
dp[m-1][n-1][o-1]=Math.max(Math.max(f1,f2),f3);
return dp[m-1][n-1][o-1];
}

}

}

Sir it is showing TLE with memoization …can u tell what is the problem with the code???