Dynamic programming MCQs repeatedly test overlapping subproblems, optimal substructure, and memoization versus tabulation. Nine of the 12 questions below were set in real papers, from UGC NET 2019 through GATE 2026, and each carries its exam and year. Attempt each one before reading its explanation. Question 12 has its own solved page, linked where it appears, and the same ideas are taught in order inside the Algorithms learn module.
What dynamic programming actually is: Questions 1 to 3
Dynamic programming is recursion plus reuse. It applies when the same subproblems overlap and an optimal answer can be built from optimal sub-answers.
Question 1: Advantage over naive recursion, TPSC 2024
What is the main advantage of using dynamic programming compared to a naive recursive approach ?
(a) It uses less memory
(b) It requires less input data
(c) It avoids redundant calculations
(d) It guarantees faster execution time
Answer: (c). Naive recursion can solve the same subproblem repeatedly; DP stores and reuses its result. The table usually costs extra memory, so (a) fails. Option (d) is too absolute because DP can add overhead when subproblems do not repeat.
Question 2: The property that does not belong
Which of the following is not a property of dynamic programming?
(a) Overlapping subproblems
(b) Optimal substructure
(c) Greedy choice
(d) Memoization
Answer: (c). A greedy algorithm commits to a local best choice, while DP compares subproblem results. Options (a) and (b) qualify a problem for DP; memoization is a standard DP technique.
Question 3: Recognising DP characteristics, TPSC 2025
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.
Answer: (c). Sequential processing can describe any loop. Memoization, overlapping subproblems, and optimal substructure identify DP. Read the capitalised NOT carefully.
Memoization versus tabulation: Questions 4 and 5
Memoization is top-down: recurse and cache a state when it is first computed. Tabulation is bottom-up: fill states in dependency order. Both normally spend memory to save time.
Question 4: Purpose of memoization, IBPS 2024
What is the primary purpose of memoization in Dynamic Programming?
(a) To reduce memory allocation during execution
(b) To store intermediate results of repeated subproblems
(c) To increase recursion depth in algorithms
(d) To execute multiple functions simultaneously
(e) To convert iterative solutions into recursive solutions
Answer: (b). The cache stores a subproblem answer on first computation, making repeats constant-time lookups. Memoization spends memory, so (a) is backwards. Option (e) is the reverse of what memoization does: it keeps the recursive shape and only adds a cache in front of it.
Question 5: The top-down trade, HPSC 2021
What happens when a top-down approach of dynamic programming is applied to any problem?
(a) It increases both the time complexity and the space complexity
(b) It increases the space complexity and decreases the time complexity
(c) It increases the time complexity and decreases the space complexity
(d) It decreases both the time complexity and the space complexity
Answer: (b). Against plain recursion on a DP-suitable problem, the memo table adds space for one entry per distinct state. In return each state is computed once instead of being reached down many paths, so time falls while space rises. Options (a), (c) and (d) each move at least one of the two the wrong way.
Fibonacci, the worked example every exam reuses: Questions 6 and 7
For naive fib(5), let T(n) count calls. With T(0) = T(1) = 1 and T(n) = T(n-1) + T(n-2) + 1, we get T(2) = 3, T(3) = 5, T(4) = 9, and T(5) = 15. The call tree contains fib(5) once, fib(4) once, fib(3) twice, fib(2) three times, fib(1) five times, and fib(0) three times. The check is 1 + 1 + 2 + 3 + 5 + 3 = 15.
With memoization, each state from fib(0) through fib(5) is computed once, which is six computations. In general, the usual exponential O(2^n) bound falls to O(n), using an O(n) table.
Question 6: Fibonacci time complexity
The time complexities of computing the Fibonacci series with and without dynamic programming are, respectively:
(a) O(2^n) and O(n)
(b) O(2^n) and O(2^n)
(c) O(n) and O(2^n)
(d) O(n) and O(3^n)
Answer: (c). DP solves each of the n + 1 states once, giving O(n). Plain recursion reaches 15 calls at n = 5 and grows exponentially, giving the O(2^n) bound here. Option (a) reverses the order.
Question 7: Fibonacci space complexity
What is the space complexity of the Fibonacci sequence problem when solved using dynamic programming?
(a) O(1)
(b) O(n)
(c) O(n²)
(d) O(n log n)
Answer: (b). Standard memoization or tabulation stores n + 1 entries, giving O(n) space. Retaining only the previous two values can reduce this to O(1), but that is beyond the table-based formulation tested.
The four design steps in order: Questions 8 and 9
The canonical sequence is: characterize the structure of an optimal solution, recursively define its value, compute that value, and construct an optimal solution from the computed information.
Question 8: Ordering the steps, UGC NET 2025
When developing a dynamic programming algorithm, the sequence of steps followed is:
A. Construct an optimal solution from computed information.
B. Recursively define the value of an optimal solution.
C. Characterize the structure of an optimal solution.
D. Compute the value of an optimal solution, typically in a bottom-up fashion.
(a) B, C, A, D
(b) B, A, C, D
(c) C, B, A, D
(d) C, B, D, A
Answer: (d). Map the sequence: characterize C, define B, compute D, construct A. The traps place construction before computation, although reconstruction needs the completed table.
Question 9: What DP and greedy share, UGC NET 2019
Consider the following steps:
S1: Characterize the structure of an optimal solution
S2: Compute the value of an optimal solution in bottom-up fashion
Which of the following step(s) is/are common to both dynamic programming and greedy algorithms?
(a) Only S1
(b) Only S2
(c) Both S1 and S2
(d) Neither S1 nor S2
Answer: (a). Both methods characterize optimal structure. Bottom-up table computation is DP-specific. A greedy algorithm makes one justified choice at a time instead.
Which problems are dynamic programming problems: Questions 10 and 11
A problem suits DP when subproblems repeat and their best answers compose into a larger best answer. Classic examples include Fibonacci, longest common subsequence, knapsack, matrix-chain multiplication, optimal BST, LIS, and Floyd-Warshall.
Question 10: Classic DP problems, TPSC 2025
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
Answer: (d). Optimal BST reuses optimal subtrees over key ranges. LCS reuses states formed by prefixes of two strings. The 0/1 knapsack reuses item-count and capacity states. For the last pattern with a full recurrence and table, read the 0/1 Knapsack walkthrough.
Question 11: Classical LIS complexity, IBPS 2024
What is the time complexity of the classical Dynamic Programming approach using nested loops for the LIS problem?
(a) O(n)
(b) O(n log n)
(c) O(n²)
(d) O(log n)
(e) O(n³)
Answer: (c). For every i, the recurrence checks each earlier j < i and may set dp[i] = 1 + dp[j]. Two nested loops take O(n²). An O(n log n) patience-sorting method exists, but the question asks for classical nested-loop DP.
Filling a DP table in the right order: Question 12
Tabulation works only when every dependency is ready before its dependent cell is computed. The GATE 2026 table-fill question below tests two orders that both satisfy that rule.
Question 12: Two dependency-respecting orders, GATE 2026
Consider a table T where the entries T[i][j], 0 <= i, j <= n, represent optimal subproblem costs in a dynamic programming algorithm. The recursive formulation is:
T[0][k] = T[k][0] = 1 for k = 0, 1, 2, ..., n
T[i][j] = 2T[i-1][j] + 3T[i][j-1] for 1 <= i, j <= n
Assume for both algorithms below every T[i][j] has been initialized to 1.
Algorithm B1: for i = 1 to n, for j = 1 to n: T[i][j] = 2T[i-1][j] + 3T[i][j-1]
Algorithm B2: for s = 2 to 2n, for i = 1 to n, for j = 1 to n: if (i + j == s) then T[i][j] = 2T[i-1][j] + 3T[i][j-1]
Algorithm Bk (k in {1, 2}) is correct iff it computes every T[i][j] per the recursive formulation. Which one of the following statements is true?
(a) Both algorithms B1 and B2 are correct
(b) Algorithm B1 correct, B2 incorrect
(c) Algorithm B2 correct, B1 incorrect
(d) Both incorrect
Answer: (a). T[i][j] needs the cell above, T[i-1][j], and the cell to its left, T[i][j-1]. B1 moves row by row from left to right, so both are ready. B2 moves through increasing anti-diagonals with s = i + j. Each dependency has index sum s - 1, so it was processed earlier.
For a numerical check, both orders begin with T[1][1] = 2T[0][1] + 3T[1][0] = 2(1) + 3(1) = 5. They are two valid topological orders of the same dependency graph.
The short version and your next step
DP needs overlapping subproblems and optimal substructure.
Memoization caches top-down; tabulation fills bottom-up. Both trade space for time.
Fibonacci shows the standard O(2^n) to O(n) improvement with an O(n) table.
The design order is characterize, define, compute, construct.
Any table-fill order is correct when it computes every dependency first.
More than 20 practice questions sit on introductory dynamic programming alone, so 12 is a start rather than a finish. The GATE 2026 question above is solved inside the Algorithms module of GATE Guidance by Sanchit Sir. Use these 12 as a diagnostic, revise the idea behind every miss, then browse the wider GATE CS preparation options for your next topic.
