Vidyalelo
Data Structure · Q144

Dynamic Programming in Data Structures

Programming · Data Structure · question 144

Q144

Consider the following dynamic programming implementation of the longest common subsequence problem: #include #include int max_num(int a, int b) if(a > b) return a; return b; int lcs(char *str1, char *str2) int i,j,len1,len2; len1 = strlen(str1); len2 = strlen(str2); int arr[len1 + 1][len2 + 1]; for(i = 0; i <= len1; i++) arr[i][0] = 0; for(i = 0; i <= len2; i++) arr[0][i] = 0; for(i = 1; i <= len1; i++) for(j = 1; j <= len2; j++) if(str1[i-1] == str2[j - 1]) ______________; else arr[i][j] = max_num(arr[i - 1][j], arr[i][j - 1]); return arr[len1][len2]; int main() char str1[] = " abcedfg", str2[] = "bcdfh"; int ans = lcs(str1,str2); printf("%d",ans); return 0; Which of the following lines completes the above code?

A.
arr[i][j] = 1 + arr[i][j].
B.
arr[i][j] = 1 + arr[i - 1][j - 1].
Answer
C.
arr[i][j] = arr[i - 1][j - 1].
D.
arr[i][j] = arr[i][j].

Answer: Option B

Solution

Answer: Option B
No explanation is given for this question Let's Discuss on Board