Consider the following dynamic programming implementation:
#include<stdio.h>
#include<string.h>
int max(int a, int b)
{
if(a > b)
return a;
return b;
}
int min_ins(char *s)
{
int len = strlen(s), i, j;
int arr[len + 1][len + 1];
char rev[len + 1];
strcpy(rev, s);
strrev(rev);
for(i = 0;i <= len; i++)
arr[i][0] = 0;
for(i = 0; i <= len; i++)
arr[0][i] = 0;
for(i = 1; i <= len; i++)
{
for(j = 1; j <= len; j++)
{
if(s[i - 1] == rev[j - 1])
arr[i][j] = arr[i - 1][j - 1] + 1;
else
arr[i][j] = max(arr[i - 1][j], arr[i][j - 1]);
}
}
return _____________;
}
int main()
{
char s[] = "abcda";
int ans = min_ins(s);
printf("%d",ans);
return 0;
}
Which of the following lines should be added to complete the code?
#include<stdio.h>
#include<string.h>
int max(int a, int b)
{
if(a > b)
return a;
return b;
}
int min_ins(char *s)
{
int len = strlen(s), i, j;
int arr[len + 1][len + 1];
char rev[len + 1];
strcpy(rev, s);
strrev(rev);
for(i = 0;i <= len; i++)
arr[i][0] = 0;
for(i = 0; i <= len; i++)
arr[0][i] = 0;
for(i = 1; i <= len; i++)
{
for(j = 1; j <= len; j++)
{
if(s[i - 1] == rev[j - 1])
arr[i][j] = arr[i - 1][j - 1] + 1;
else
arr[i][j] = max(arr[i - 1][j], arr[i][j - 1]);
}
}
return _____________;
}
int main()
{
char s[] = "abcda";
int ans = min_ins(s);
printf("%d",ans);
return 0;
}A. arr[len][len]
B. len + arr[len][len]
C. len
D. len - arr[len][len]
Answer: Option D

Join The Discussion