Dynamic Programming Questions and Answers

Q: Consider a matrix multiplication chain F1F2F3F4F5, where matrices F1, F2, F3, F4 and F5 are of dimensions 2×25, 25×3, 3×16, 16×1 and 1×1000, respectively. In the parenthesization of F1F2F3F4F5 that minimizes the total number of scalar multiplications, the explicitly computed pairs is/are

The only explicitly computed pair is \(F_{3}F_{4}\).F4 is 16 × 1, so multiplying towards it collapses the inner dimension to 1. The minimum-cost parenthesization is \(((F_{1}(F_{2}(F_{3}F_{4})))F_{5})\):\[ \begin{aligned} F_{3}F_{4} &: 3 \cdot 16 \cdot 1 = 48 \\ F_{2}(F_{3}F_{4}) &: 25 \cdot 3 \cdot 1 = 75 \\ F_{1}(\ldots) &: 2 \cdot 25 \cdot 1 = 50 \\ (\ldots)F_{5} &: 2 \cdot 1 \cdot 1000 = 2000 \\ \text{total} &= 2173 \end{aligned} \]Here \(F_{3}F_{4}\) is the only product of two adjacent original matrices. The alternatives cost more: \(((F_{1}F_{2})(F_{3}F_{4}))F_{5}\) costs 150 + 48 + 6 + 2000 = 2204, any order that computes \(F_{4}F_{5}\) pays 16,000 for that step alone, and \(F_{2}F_{3}\) alone costs 1,200.

Q: Algorithm \(B_{k}, k \in \{1,2\}\) is said to be correct if and only if it calculates the correct values of T[i][j], for all \(0 \le i,j \le n\), (as per the recursive formulation) at the end of the execution of the algorithm \(B_{k}\).Which one of the following statements is true?

Both algorithms B1 and B2 are correct.Each entry T[i][j] depends on two others: the one above, T[i-1][j], and the one to its left, T[i][j-1]. An algorithm is correct if both of these already hold their final values when T[i][j] is computed. Row 0 and column 0 are base cases, already equal to 1.B1 fills the table row by row, left to right. When it reaches T[i][j], row i - 1 is complete, and T[i][j-1] was computed just before in the same row. Both dependencies are ready.B2 fills the table by anti-diagonals, s = i + j from 2 to 2n, computing only the cells with i + j = s in each pass. Both dependencies of T[i][j] have index sum s - 1, so they were computed in the previous pass (or are base cases). Both are ready.Since both orders respect the dependencies, both give the correct table, ruling out the three options that call either algorithm incorrect. The wasted iterations of B2 make it slower (Θ(n3) work) but not wrong.

Q: The Floyd-Warshall algorithm for all-pair shortest paths computation is based on

Floyd-Warshall is based on the Dynamic Programming paradigm.It computes \(d_{k}(i, j)\), the shortest path from \(i\) to \(j\) using only the first \(k\) vertices as intermediates, from the previous table:\[ \begin{aligned} d_{k}(i,j) = \min(&d_{k-1}(i,j), \\ &d_{k-1}(i,k) + d_{k-1}(k,j)) \end{aligned} \]This builds the solution from overlapping subproblems stored in a table, the defining feature of dynamic programming, and runs in \(O(n^{3})\).It is not greedy: Dijkstra’s algorithm is the greedy shortest-path method, fixing one vertex at a time. It is not divide-and-conquer, which splits a problem into independent subproblems; the subproblems here overlap and are reused.

Q: Which of the following problems can be solved by Dynamic Programming (DP) ?

The answer is All of the above.Each of the three problems has the two properties dynamic programming needs, overlapping subproblems and optimal substructure. The optimal binary search tree, the longest common subsequence and the 0/1 knapsack problem are all standard textbook DP problems, solved by filling a table of subproblem results.Choosing any one of them alone would leave out the other two.

Q: Which technique does dynamic programming use to improve efficiency ?

Dynamic programming relies on memoization.Dynamic programming applies to problems whose subproblems overlap. It stores the answer to each subproblem the first time it is solved, either top-down in a memo table or bottom-up in a tabulation, and reuses it instead of recomputing it. Naive recursive Fibonacci takes exponential time, while the memoized version is linear.Divide and conquer splits a problem into independent subproblems that do not repeat, as in merge sort, so there is nothing to reuse. Backtracking explores choices and undoes them. A greedy approach makes one locally best choice at each step without revisiting it.

Q: Which of the following is NOT a characteristic of dynamic programming ?

The one that is not a characteristic is solving problems in a sequential manner.Dynamic programming rests on two properties: overlapping sub-problems, which are solved once and their results stored (memoization or a table), and optimal sub-structure, where an optimal solution is built from optimal solutions of sub-problems.Options A, B and D describe exactly those features. 'Solving problems in a sequential manner' describes no defining feature of the method, so it is the odd one out.

Q: If sub-problems are such that each solution can be used at a later point (the sub-problems need not be homogenous), which strategy can be used ?

The strategy is Dynamic programming.Dynamic programming suits problems whose sub-problems overlap: the same sub-problem comes up again and again, so its solution is computed once, stored in a table, and used later whenever it is needed. Computing Fibonacci numbers bottom-up is the simplest example.Divide and conquer splits a problem into independent sub-problems that are solved separately and not reused. Backtracking searches a tree of choices and abandons dead ends; it does not store solutions for later use.

Direction for [ Question No: 1 To 1 ] :

Assume that multiplying a matrix G₁ of dimension \(p \times q\) with another matrix G₂ of dimension \(q \times r\) requires \(pqr\) scalar multiplications. Computing the product of \(n\) matrices G₁G₂G₃...G_n can be done by parenthesizing in different ways. Define G_i G_i+1 as an explicitly computed pair for a given paranthesization if they are directly multiplied. For example, in the matrix multiplication chain G₁G₂G₃G₄G₅G₆ using parenthesization (G₁(G₂G₃))(G₄(G₅G₆)), G₂G₃ and G₅G₆ are the only explicitly computed pairs.

Consider a matrix multiplication chain F₁F₂F₃F₄F₅, where matrices F₁, F₂, F₃, F₄ and F₅ are of dimensions 2×25, 25×3, 3×16, 16×1 and 1×1000, respectively. In the parenthesization of F₁F₂F₃F₄F₅ that minimizes the total number of scalar multiplications, the explicitly computed pairs is/are

A.\(F_{1}F_{2}\) and \(F_{3}F_{4}\) only
B.\(F_{2}F_{3}\) only
C.\(F_{3}F_{4}\) only
D.\(F_{1}F_{2}\) and \(F_{4}F_{5}\) only

Exam Year(s)

GATE CS - 2018,

Answer: C

The only explicitly computed pair is \(F_{3}F_{4}\).

F₄ is 16 × 1, so multiplying towards it collapses the inner dimension to 1. The minimum-cost parenthesization is \(((F_{1}(F_{2}(F_{3}F_{4})))F_{5})\):

\[ \begin{aligned} F_{3}F_{4} &: 3 \cdot 16 \cdot 1 = 48 \\ F_{2}(F_{3}F_{4}) &: 25 \cdot 3 \cdot 1 = 75 \\ F_{1}(\ldots) &: 2 \cdot 25 \cdot 1 = 50 \\ (\ldots)F_{5} &: 2 \cdot 1 \cdot 1000 = 2000 \\ \text{total} &= 2173 \end{aligned} \]

Here \(F_{3}F_{4}\) is the only product of two adjacent original matrices. The alternatives cost more: \(((F_{1}F_{2})(F_{3}F_{4}))F_{5}\) costs 150 + 48 + 6 + 2000 = 2204, any order that computes \(F_{4}F_{5}\) pays 16,000 for that step alone, and \(F_{2}F_{3}\) alone costs 1,200.

Discuss in Forum

Direction for [ Question No: 2 To 2 ] :

Consider a table T, where the elements T[i][j], \(0 \le i,j \le n\), represent the cost of the optimal solutions of different subproblems of a problem that is being solved using a dynamic programming algorithm. The recursive formulation to compute the table entries is as follows:

\(T[0][k] = T[k][0] = 1\) for \(k = 0,1,2,\ldots,n\)
\(T[i][j] = 2T[i-1][j] + 3T[i][j-1]\) for \(1 \le i,j \le n\)

Consider the following two algorithms to compute entries of T. Assume that for both the algorithms, for all \(0 \le i,j \le n\), T[i][j] has been initialized to 1.

Algorithm \(B_{1}\): For i = 1, 2, ..., n
For j = 1, 2, ..., n
\(T[i][j] = 2T[i-1][j] + 3T[i][j-1]\)

Algorithm \(B_{2}\): For s = 2, 3, ..., 2n
For i = 1, 2, ..., n
For j = 1, 2, ..., n
If (i + j == s)
\(T[i][j] = 2T[i-1][j] + 3T[i][j-1]\)

Algorithm \(B_{k}, k \in \{1,2\}\) is said to be correct if and only if it calculates the correct values of T[i][j], for all \(0 \le i,j \le n\), (as per the recursive formulation) at the end of the execution of the algorithm \(B_{k}\).

Which one of the following statements is true?

A.Both algorithms \(B_{1}\) and \(B_{2}\) are correct
B.Algorithm \(B_{1}\) is correct, but algorithm \(B_{2}\) is incorrect
C.Algorithm \(B_{2}\) is correct, but algorithm \(B_{1}\) is incorrect
D.Both algorithms \(B_{1}\) and \(B_{2}\) are incorrect

Exam Year(s)

GATE CS - 2026,

Answer: A

Both algorithms B₁ and B₂ are correct.

Each entry T[i][j] depends on two others: the one above, T[i-1][j], and the one to its left, T[i][j-1]. An algorithm is correct if both of these already hold their final values when T[i][j] is computed. Row 0 and column 0 are base cases, already equal to 1.

B₁ fills the table row by row, left to right. When it reaches T[i][j], row i - 1 is complete, and T[i][j-1] was computed just before in the same row. Both dependencies are ready.
B₂ fills the table by anti-diagonals, s = i + j from 2 to 2n, computing only the cells with i + j = s in each pass. Both dependencies of T[i][j] have index sum s - 1, so they were computed in the previous pass (or are base cases). Both are ready.

Since both orders respect the dependencies, both give the correct table, ruling out the three options that call either algorithm incorrect. The wasted iterations of B₂ make it slower (Θ(n³) work) but not wrong.

Discuss in Forum

The Floyd-Warshall algorithm for all-pair shortest paths computation is based on

A.Greedy paradigm.
B.Divide-and-Conquer paradigm.
C.Dynamic Programming paradigm.
D.neither Greedy nor Divide-and-Conquer nor Dynamic Programming paradigm.

Exam Year(s)

GATE CS - 2016,

Answer: C

Floyd-Warshall is based on the Dynamic Programming paradigm.

It computes \(d_{k}(i, j)\), the shortest path from \(i\) to \(j\) using only the first \(k\) vertices as intermediates, from the previous table:

\[ \begin{aligned} d_{k}(i,j) = \min(&d_{k-1}(i,j), \\ &d_{k-1}(i,k) + d_{k-1}(k,j)) \end{aligned} \]

This builds the solution from overlapping subproblems stored in a table, the defining feature of dynamic programming, and runs in \(O(n^{3})\).

It is not greedy: Dijkstra’s algorithm is the greedy shortest-path method, fixing one vertex at a time. It is not divide-and-conquer, which splits a problem into independent subproblems; the subproblems here overlap and are reused.

Discuss in Forum

Which of the following problems can be solved by Dynamic Programming (DP) ?

A.Optimal Binary Search Tree
B.Longest Common Subsequence
C.Knapsack Problem
D.All of the above

Exam Year(s)

Tripura Public Service Commission - 2025,

Answer: D

The answer is All of the above.

Each of the three problems has the two properties dynamic programming needs, overlapping subproblems and optimal substructure. The optimal binary search tree, the longest common subsequence and the 0/1 knapsack problem are all standard textbook DP problems, solved by filling a table of subproblem results.

Choosing any one of them alone would leave out the other two.

Discuss in Forum

Which technique does dynamic programming use to improve efficiency ?

A.Divide and conquer
B.Memoization
C.Backtracking
D.Greedy approach

Exam Year(s)

Tripura Public Service Commission - 2026,

Answer: B

Dynamic programming relies on memoization.

Dynamic programming applies to problems whose subproblems overlap. It stores the answer to each subproblem the first time it is solved, either top-down in a memo table or bottom-up in a tabulation, and reuses it instead of recomputing it. Naive recursive Fibonacci takes exponential time, while the memoized version is linear.

Divide and conquer splits a problem into independent subproblems that do not repeat, as in merge sort, so there is nothing to reuse. Backtracking explores choices and undoes them. A greedy approach makes one locally best choice at each step without revisiting it.

Discuss in Forum

Which of the following is NOT a characteristic of dynamic programming ?

A.Memoization, which involves storing the results of expensive function calls and reusing them.
B.Breaking a problem into smaller overlapping sub-problems.
C.Solving problems in a sequential manner.
D.Dynamic programming can be used for problems where the solution has an optimal sub-structure.

Exam Year(s)

Tripura Public Service Commission - 2025,

Answer: C

The one that is not a characteristic is solving problems in a sequential manner.

Dynamic programming rests on two properties: overlapping sub-problems, which are solved once and their results stored (memoization or a table), and optimal sub-structure, where an optimal solution is built from optimal solutions of sub-problems.

Options A, B and D describe exactly those features. 'Solving problems in a sequential manner' describes no defining feature of the method, so it is the odd one out.

Discuss in Forum

If sub-problems are such that each solution can be used at a later point (the sub-problems need not be homogenous), which strategy can be used ?

A.Dynamic
B.Divide and conquer
C.Backtracking
D.None of the above

Exam Year(s)

Tripura Public Service Commission - 2019,

Answer: A

The strategy is Dynamic programming.

Dynamic programming suits problems whose sub-problems overlap: the same sub-problem comes up again and again, so its solution is computed once, stored in a table, and used later whenever it is needed. Computing Fibonacci numbers bottom-up is the simplest example.

Divide and conquer splits a problem into independent sub-problems that are solved separately and not reused. Backtracking searches a tree of choices and abandons dead ends; it does not store solutions for later use.

Discuss in Forum

Which one of the following binary search tree is optimal, if probabilities of successful search and unsuccessful search are same ?

Exam Year(s)

UGC NET - 2012,

Answer: D

When the probabilities of successful and unsuccessful searches are all the same, the optimal binary search tree is the one with the least path length, which is the one with the smallest height. With three keys and four external nodes, the balanced tree with B at the root and C and A as its children, option (D), has every external node at depth 2. The tree in (A) is a chain that puts two external nodes at depth 3, and the trees in (B) and (C) each have external nodes at depth 3 as well, so they cost more. The answer is option (D).

Discuss in Forum

Loading…

Topics

Other Subjects

Tags: Dynamic Programming Questions and Answers || Dynamic Programming MCQ Questions and Answers || Dynamic Programming GK Questions and Answers || Dynamic Programming GK MCQ Questions || Dynamic Programming Multiple Choice Questions and Answers || Dynamic Programming GK || GK on Dynamic Programming || Data Structures and Algorithms Questions and Answers || Data Structures and Algorithms MCQ Questions and Answers || Data Structures and Algorithms GK Questions and Answers || GK on Data Structures and Algorithms

Dynamic Programming Questions and Answers

Direction for [ Question No: 1 To 1 ] :

Direction for [ Question No: 2 To 2 ] :

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications