Dynamic Programming must be used. Use java, and include a main method that prove

Question

Dynamic Programming must be used. Use java, and include a main method that proves the correctness of the algorithm. Complexity must be O(mn).

This is NOT just a Longest Common Subsequence Dynamic Programming problem. This problem is asking to find the length of the longest common subsequence where we are allowed to also change at most one element of Array A. Do not answer this if you are not going to answer the problem correctly.

Problem 5: (5 + 2 points) Given two sequences of symbols A and B of lengths m and n resepec- tively, design an algorithm for computing the length of the longest possible common subsequence if we are allowed to change at most one element of A. For example, if A = [a, a, b, b, b) and B-a, c, c,b), then the answer is 3, because we can change the second symbol in A and get A = a, c, b, b,b]. After that, the longest common subsequence is [a, c, b]. The complexity of the algorithm has to be O(mn).

Explanation / Answer

To solve the problem, the essense is to use dynamic programming. We will define a 3D matrix dp[][][], where dp[i][j][k] defines the LCS for the first i numbers of first array, first j number of second array when we are allowed to change at max k number in the first array. In our case, k=1. Therefore, recursion will look like

Java code imlementing the above algo is given below:

import java.util.*;
import java.lang.*;

public class LCS_K {

static int ans;
final static int MAX=100;

static int lcs(int dp[][][], char arr1[], int n,char arr2[], int m, int k)
{
// If any of two array is over.
if (k < 0)
return -1;
if (n < 0 || m < 0)
return 0;

// Making a reference variable to dp[n][m][k]
ans = dp[n][m][k];

// If the answer value is already calculated, return that value.
if (ans != -1)
return ans;

// calculating the longest common subsequence with no changes made.
ans = Math.max(lcs(dp, arr1, n - 1, arr2, m, k), lcs(dp, arr1, n, arr2, m - 1, k));

// calculating the LCS when array element are same.
if (arr1[n] == arr2[m])
ans = Math.max(ans, 1 + lcs(dp, arr1, n - 1,
arr2, m - 1, k));

// calculating longest common subsequence with changes made.
ans = Math.max(ans, 1 + lcs(dp, arr1, n - 1,
arr2, m - 1, k - 1));

return ans;
}



public static void main(String []args){

char arr1[] = new char[] { 'a','a','b','b','b' };
char arr2[] = new char[] { 'a','c','c','b' };
int n = arr1.length;
int m = arr2.length;;

int dp[][][]=new int[MAX][MAX][MAX];
  
for (int i=0;i<MAX;i++)
{
for (int j=0;j<MAX;j++)
{
for (int k=0;k<MAX;k++)
dp[i][j][k]=-1;
}
}
  
System.out.println("Length of LCS where 1 array elemnt can be changed: " + lcs(dp, arr1, n-1, arr2, m-1, 1));
}
}

Here the input is:

A={ 'a','a','b','b','b' };
B= { 'a','c','c','b' };

Sample Output:

Length of LCS where 1 array elemnt can be changed: 3

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.