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

Memoization is the technique in which previously calculated values are stored, so that, these values can be used to solve other subproblems.

A greedy algorithm gives optimal solution for all subproblems, but when these locally optimal solutions are combined it may NOT result into a globally optimal solution. Hence, a greedy algorithm CANNOT be used to solve all the dynamic programming problems.

Dynamic programming calculates the value of a subproblem only once, while other methods that don't take advantage of the overlapping subproblems property may calculate the value of the same subproblem several times. So, dynamic programming saves the time of recalculation and takes far less time as compared to other methods that don't take advantage of the overlapping subproblems property.

In divide and conquer, the problem is divided into smaller non-overlapping subproblems and an optimal solution for each of the subproblems is found. The optimal solutions are then combined to get a global optimal solution. For example, mergesort uses divide and conquer strategy.

Overlapping subproblems is the property in which value of a subproblem is used several times.

Optimal substructure is the property in which an optimal solution is found for the problem by constructing optimal solutions for the subproblems.

A problem that can be solved using dynamic programming possesses overlapping subproblems as well as optimal substructure properties.

The line arr[num_of_dice][S] completes the above code.

Since there are 10 dice and the minimum value each die can take is 1, the minimum possible sum is 10. Hence, a sum of 4 cannot be achieved.

The sum will be maximum when all the faces show a value f. The sum in this case will be n*f.

The sum will be minimum when all the faces show a value 1. The sum in this case will be n.

The sum of 11 can be achieved when the dice show {6, 5} or {5, 6}.

The total number of permutations that can be obtained is 6 * 6 * 6 = 216.

Each die can take f values and there are n dice. So, the total number of permutations is fff...n times.

Brute force, Recursion and Dynamic Programming can be used to solve the dice throw problem.

The following lines should be added:

False[row][col] += False[row][pos] * False[pos+1][col];

True[row][col] += t_row_pos * t_pos_col + False[row][pos] * False[pos+1][col];

The number of ways will be maximum when all the possible parenthesizations result in a true value. The number of possible parenthesizations is given by the nth catalan number.

The nth Catalan number gives the total number of ways of parenthesizing an expression with n + 1 terms.

The expression can be parenthesized as (T | F) ∧ T, so that the output is F (false).

The expression can be parenthesized as (T & F) ∧ T or T & (F ∧ T), so that the output is T.