41. In Dynamic Programming, what does the term "subproblem" refer to?
42. Which problem is best solved using Dynamic Programming by maintaining a 2D table to store results?
43. What is the time complexity of the Dynamic Programming solution for the "Longest Palindromic Substring" problem?
44. How does the concept of "overlapping subproblems" apply to the "Knapsack Problem" in Dynamic Programming?
45. In the context of Dynamic Programming, what is the typical use of "backtracking"?
46. Consider the two strings ""(empty string) and "abcd". What is the edit distance between the two strings?
47. What is the output of the following code?
#include<stdio.h>
#include<string.h>
int max_num(int a, int b)
{
if(a > b)
return a;
return b;
}
int lps(char *str1)
{
int i,j,len;
len = strlen(str1);
char str2[len + 1];
strcpy(str2, str1);
strrev(str2);
int arr[len + 1][len + 1];
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(str1[i-1] == str2[j - 1])
arr[i][j] = 1 + arr[i - 1][j - 1];
else
arr[i][j] = max_num(arr[i - 1][j], arr[i][j - 1]);
}
}
return arr[len][len];
}
int main()
{
char str1[] = "abcd";
int ans = lps(str1);
printf("%d",ans);
return 0;
}
#include<stdio.h>
#include<string.h>
int max_num(int a, int b)
{
if(a > b)
return a;
return b;
}
int lps(char *str1)
{
int i,j,len;
len = strlen(str1);
char str2[len + 1];
strcpy(str2, str1);
strrev(str2);
int arr[len + 1][len + 1];
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(str1[i-1] == str2[j - 1])
arr[i][j] = 1 + arr[i - 1][j - 1];
else
arr[i][j] = max_num(arr[i - 1][j], arr[i][j - 1]);
}
}
return arr[len][len];
}
int main()
{
char str1[] = "abcd";
int ans = lps(str1);
printf("%d",ans);
return 0;
}48. For which of the following pairs of strings is the edit distance maximum?
49. Consider the recursive implementation to find the nth fibonacci number:
Which line would make the implementation complete?
int fibo(int n)
if n <= 1
return n
return __________
Which line would make the implementation complete?
int fibo(int n)
if n <= 1
return n
return __________50. What is the time complexity of the brute force algorithm used to solve the balanced partition problem?
Read More Section(Dynamic Programming in Data Structures)
Each Section contains maximum 100 MCQs question on Dynamic Programming in Data Structures. To get more questions visit other sections.