Dynamic Programming in Data Structure And Algorithm : Practice MCQ Questions & Answers with Explanations

If the matrix size is 1×1 then the element itself is the maximum sum of that 1×1 matrix. If all elements are zero, then the sum of any submatrix of the given matrix is zero. If all elements are negative, then the maximum element in that matrix is the highest sum in that matrix which is again 1X1 submatrix of the given matrix. Hence all three statements are correct.

When all the elements of a matrix are positive, the maximum sum rectangle is the 2D matrix itself.

Brute force, Recursion and Dynamic programming can be used to find the submatrix that has the maximum sum.

The space complexities are as follows:

Dynamic programming: O(n)

Recursion: O(1)

Binomial coefficients: O(1).

The time complexities are as follows:

Dynamic programming: O(n^{2})

Recursion: Exponential

Binomial coefficients: O(n).

The line arr[i] += arr[j] * arr[k] reflects the recursive formula (Cn = \sumCi*C(n-i)).

All of the mentioned methods can be used to find the nth Catalan number.

Counting the number of Dyck words, Counting the number of expressions containing n pairs of parenthesis, Counting the number of ways in which a convex polygon can be cut into triangles by connecting vertices with straight lines are the applications of Catalan numbers where as creation of head and tails for a given number of tosses is an application of Pascal's triangle.

Catalan numbers are given by: (2n!)/((n+1)!n!).

First Catalan number is given by n = 0.

So the 6th Catalan number will be given by n = 5, which is 42.

Catalan numbers are given by: (2n!)/((n+1)!n!).

For n = 0, we get C0 = 1.

For n = 3, we get C3 = 5.

For n = 4, we get C4 = 14.

For n = 5, we get C3 = 42.

arr[len][len] contains the length of the longest palindromic subsequence. So, len - arr[len][len] gives the minimum number of insertions required to form a palindrome.

A variation of longest common subsequence can be used to solve the minimum number of insertions to form a palindrome problem.

The given string is already a palindrome. So, no insertions are required.

The string can be converted to "efgfe" by inserting "f" or to "egfge" by inserting "g". Thus, only one insertion is required.

In the worst case, the minimum number of insertions to be made to convert the string into a palindrome is equal to length of the string minus one. For example, consider the string "abc". The string can be converted to "abcba" by inserting "a" and "b". The number of insertions is two, which is equal to length minus one.

In string of length one, string with all same characters and a palindromic string the no of insertions is zero since the strings are already palindromes. To convert a non-palindromic string to a palindromic string, the minimum length of string to be added is 1 which is greater than all the other above cases. Hence the minimum no of insertions to form palindrome is maximum in non-palindromic strings.

Dynamic programming and recursion can be used to solve the problem.