PRACTICE • LEARN • GROW
Dynamic Programming MCQs
Solve topic-wise placement questions and improve your skills.
Dynamic Programming Progress
0 of 43 completed
0%
Topic Track
You are viewing MCQs in preview mode. Log in to select options, submit answers, and track your progress.
Log In to Answer
1
What are the two fundamental characteristics that indicate a problem can be solved using Dynamic Programming?
A.
Optimal Substructure and Overlapping Subproblems
B.
Greedy Choice Property and Divide & Conquer
C.
Sorted Input and Disjoint Sets
D.
Linear Independence and Orthogonality
Explanation & Key
Correct Answer:
2
What is the primary difference between Memoization and Tabulation in Dynamic Programming?
A.
Tabulation uses recursion while Memoization uses loops
B.
Memoization is Top-Down using recursion and caching; Tabulation is Bottom-Up using iteration and table-filling
C.
Memoization never uses memory whereas Tabulation does
D.
Tabulation is only used for NP-hard problems
Explanation & Key
Correct Answer:
3
What is the time and auxiliary space complexity of solving the 0/1 Knapsack problem with N items and capacity W using standard 2D DP?
A.
Time: O(2^N), Space: O(N)
B.
Time: O(N log W), Space: O(1)
C.
Time: O(N * W), Space: O(N * W) (optimizable to O(W) space)
D.
Time: O(W^2), Space: O(N)
Explanation & Key
Correct Answer:
4
In the 0/1 Knapsack problem with space optimization to a single 1D array of size W, in which direction must the capacity loop run?
A.
From weight[i] up to W (forward)
B.
In arbitrary random order
C.
From 0 to W alternating per item
D.
From W down to weight[i] (backward)
Explanation & Key
Correct Answer:
5
In Unbounded Knapsack (where each item can be selected unlimited times), in which direction does the 1D capacity loop run?
A.
From weight[i] up to W (forward)
B.
From W down to weight[i] (backward)
C.
From W/2 down to 0
D.
Backward with step size 2
Explanation & Key
Correct Answer:
6
What is the time complexity of finding the Longest Common Subsequence (LCS) of two strings of lengths M and N?
A.
O(M + N)
B.
O(M * N)
C.
O(2^(M+N))
D.
O(M log N)
Explanation & Key
Correct Answer:
7
What is the optimal time complexity to find the Longest Increasing Subsequence (LIS) of an array of size N using Patience Sorting / Binary Search?
A.
O(N^2)
B.
O(N)
C.
O(N log N)
D.
O(2^N)
Explanation & Key
Correct Answer:
8
What is the space complexity to compute the N-th Fibonacci number using Dynamic Programming?
A.
O(N) space strictly required
B.
O(N^2) space
C.
O(log N) auxiliary space only
D.
O(1) auxiliary space using two variables
Explanation & Key
Correct Answer:
9
What is the time complexity of the Matrix Chain Multiplication problem for N matrices using DP?
A.
O(N^3)
B.
O(N^2)
C.
O(2^N)
D.
O(N log N)
Explanation & Key
Correct Answer:
10
What is the recurrence relation for Edit Distance (Levenshtein Distance) between string S1[0...i-1] and S2[0...j-1] when characters DO NOT match?
A.
`dp[i-1][j-1] + 2`
B.
`1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])` (Delete, Insert, Replace)
C.
`max(dp[i-1][j], dp[i][j-1])`
D.
`dp[i-1][j] + dp[i][j-1]`
Explanation & Key
Correct Answer:
11
In the Coin Change Problem (Minimum Coins to make amount A), what does `dp[amount]` represent?
A.
The total number of ways to arrange coins
B.
The denomination of the largest coin used
C.
The minimum number of coins needed to make change for `amount`
D.
The probability of making change
Explanation & Key
Correct Answer:
12
In the Coin Change Problem 2 (Total Number of Ways to make amount A), why does the outer loop iterate over COINS and inner loop over AMOUNT?
A.
To avoid stack overflow
B.
To ensure all coin values are positive
C.
To reduce time complexity from O(N^2) to O(N)
D.
To generate combinations (uniqueness regardless of order) instead of permutations
Explanation & Key
Correct Answer:
13
What is the time complexity of Kadane's Algorithm for Maximum Subarray Sum?
A.
O(N) time and O(1) space
B.
O(N log N) time and O(N) space
C.
O(N^2) time and O(1) space
D.
O(N^3) time and O(N) space
Explanation & Key
Correct Answer:
14
What is the time complexity to solve the Palindrome Partitioning problem (Minimum cuts to partition S into palindromes) for a string of length N?
A.
O(N^3)
B.
O(N^2)
C.
O(2^N)
D.
O(N log N)
Explanation & Key
Correct Answer:
15
What is the time complexity to find the optimal Binary Search Tree (Optimal BST) for N keys with search probabilities?
A.
O(N log N)
B.
O(2^N)
C.
O(N^3) (reducible to O(N^2) via Knuth's Optimization)
D.
O(N)
Explanation & Key
Correct Answer:
16
What is Bitmask Dynamic Programming primarily used for?
A.
Sorting large arrays in linear time
B.
Bitwise image compression in memory
C.
Balancing Red-Black trees
D.
Problems involving small set sizes (N <= 20) where subsets are represented as integer bit patterns (e.g., TSP)
Explanation & Key
Correct Answer:
17
What is the time complexity of the Travelling Salesperson Problem (TSP) using the Held-Karp algorithm (Bitmask DP)?
A.
O(N^2 * 2^N)
B.
O(N!)
C.
O(2^N)
D.
O(N^3)
Explanation & Key
Correct Answer:
18
In Tree DP, how are subproblem solutions typically propagated?
A.
Top-down using Breadth-First Search from root to leaves
B.
Bottom-up using Postorder DFS from leaf nodes to the root
C.
By sorting nodes by key value
D.
Using matrix diagonalization
Explanation & Key
Correct Answer:
19
What is the recurrence relation for the "House Robber" problem (`rob[i]` representing max money from first `i` houses)?
A.
`dp[i] = dp[i-1] + arr[i]`
B.
`dp[i] = min(dp[i-1], dp[i-2])`
C.
`dp[i] = max(dp[i-1], arr[i] + dp[i-2])`
D.
`dp[i] = arr[i] * dp[i-1]`
Explanation & Key
Correct Answer:
20
What is the time complexity to solve the Egg Dropping Puzzle with K eggs and N floors using DP with binary search optimization?
A.
O(K * N^2)
B.
O(2^(K+N))
C.
O(N^K)
D.
O(K * N log N)
Explanation & Key
Correct Answer:
21
Which technique optimizes DP transitions of the form `dp[i] = min_{j < i}(dp[j] + b[j] * a[i])` from O(N^2) to O(N log N) or O(N)?
A.
Convex Hull Trick (CHT)
B.
Floyd-Warshall algorithm
C.
Manacher's algorithm
D.
Fast Fourier Transform
Explanation & Key
Correct Answer:
22
What is the time complexity of finding the Longest Palindromic Subsequence (LPS) in a string of length N?
A.
O(N)
B.
O(N^2)
C.
O(2^N)
D.
O(N log N)
Explanation & Key
Correct Answer:
23
In the Subset Sum problem with N integers and target sum S, what is the time complexity using DP?
A.
O(2^N) strictly
B.
O(N log S)
C.
O(N * S) (Pseudo-polynomial time)
D.
O(S^2)
Explanation & Key
Correct Answer:
24
What is the difference between polynomial time and pseudo-polynomial time in Dynamic Programming?
A.
Pseudo-polynomial means the algorithm is randomized
B.
Polynomial time applies only to graphs
C.
There is no theoretical distinction
D.
Pseudo-polynomial algorithms are polynomial in the numeric VALUE of the input, but exponential in the bit-length representation of the input
Explanation & Key
Correct Answer:
25
How can the "Climbing Stairs" problem (can take 1 or 2 steps to reach N) be mapped mathematically?
A.
It maps directly to the Fibonacci sequence: `ways(N) = ways(N-1) + ways(N-2)`
B.
It equals 2^N
C.
It equals N * (N - 1) / 2
D.
It equals Catalan number C_N
Explanation & Key
Correct Answer:
26
What is the space complexity to solve Longest Common Subsequence of strings of lengths M and N when only the LENGTH of the LCS is required?
A.
O(M * N) strictly
B.
O(min(M, N)) using two rows
C.
O(1)
D.
O(M + N)
Explanation & Key
Correct Answer:
27
What is Divide and Conquer DP Optimization applied to?
A.
Sorting arrays before running binary search
B.
Bitwise XOR convolution
C.
DP transitions `dp[i][j] = min_{k <= j}(dp[i-1][k] + C(k, j))` where optimal split point `opt(i, j) <= opt(i, j+1)` (monotonicity)
D.
Evaluating postfix expressions
Explanation & Key
Correct Answer:
28
What is the optimal substructure property in Dynamic Programming?
A.
All subproblems must have identical solutions
B.
The problem can only be solved using greedy heuristics
C.
The problem has no overlapping subproblems
D.
An optimal solution to the overall problem contains optimal solutions to its subproblems
Explanation & Key
Correct Answer:
29
In the Rod Cutting problem, what does `dp[i]` represent for a rod of length i with piece prices `p[1...i]`?
A.
The maximum revenue obtainable by cutting up a rod of length i
B.
The number of cuts made
C.
The minimum length of leftover waste
D.
The average price per inch
Explanation & Key
Correct Answer:
30
How does SOS (Sum Over Subsets) DP optimize sum queries over sub-masks from O(3^N) to O(N * 2^N)?
A.
By sorting mask bit-counts in descending order
B.
By considering one bit at a time and accumulating partial sums dimension by dimension
C.
By using Fast Fourier Transform on integers
D.
By pruning all masks with odd parity
Explanation & Key
Correct Answer:
31
In the Longest Increasing Subsequence (LIS) problem, how can the standard O(n^2) DP solution be optimized to O(n log n)?
A.
Using a tails array with Binary Search (`std::lower_bound`) to replace or extend active subsequence ends
B.
Using a hash map
C.
Sorting the array first
D.
Using Depth-First Search with pruning
Explanation & Key
Correct Answer:
32
What is the state transition formula for Edit Distance (Levenshtein Distance) when characters s1[i-1] and s2[j-1] do not match?
A.
dp[i][j] = 1 + min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]})
B.
dp[i][j] = dp[i-1][j-1]
C.
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
D.
dp[i][j] = dp[i-1][j] + dp[i][j-1]
Explanation & Key
Correct Answer:
33
In Matrix Chain Multiplication of n matrices, what is the order of subproblem evaluation in Tabulation?
A.
Increasing order of chain length L (from length 2 to n)
B.
Row by row from top to bottom
C.
Random order
D.
Decreasing order of chain length
Explanation & Key
Correct Answer:
34
Why does 1D space optimization in 0/1 Knapsack require traversing capacity w from W down to wt[i] (backwards)?
A.
Traversing forward would overwrite states from the previous row, causing the same item to be reused multiple times (turning it into Unbounded Knapsack)
B.
Backward loops execute faster on x86 processors
C.
Forward traversal results in array index out-of-bounds
D.
Backward traversal guarantees integer precision
Explanation & Key
Correct Answer:
35
In the House Robber problem, what is the recurrence relation for max loot at house i?
A.
dp[i] = max(dp[i-1], nums[i] + dp[i-2])
B.
dp[i] = nums[i] + dp[i-1]
C.
dp[i] = min(dp[i-1], nums[i])
D.
dp[i] = dp[i-1] * nums[i]
Explanation & Key
Correct Answer:
36
What is the time and space complexity of the Unique Paths in an m x n grid problem with 1D space optimization?
A.
Time: O(m * n), Space: O(n)
B.
Time: O(m + n), Space: O(1)
C.
Time: O(2^(m+n)), Space: O(m*n)
D.
Time: O(m * n), Space: O(m * n)
Explanation & Key
Correct Answer:
37
What distinguishes Bitmask Dynamic Programming from standard 2D DP?
A.
The state uses integer bit patterns (e.g., 0 to 2^n - 1) to represent subsets of visited elements or configurations
B.
It uses 64-bit floating point numbers
C.
It avoids loops using bitwise operators
D.
It only works on arrays of size 2
Explanation & Key
Correct Answer:
38
What is the base case for the Coin Change problem (finding minimum coins to make amount A)?
A.
dp[0] = 0 (0 coins required to form 0 amount), and all other dp[i] initialized to infinity
B.
dp[0] = -1
C.
dp[0] = 1
D.
dp[A] = 0
Explanation & Key
Correct Answer:
39
In the Partition Equal Subset Sum problem, what target sum must a subset sum up to for an array with total sum S?
A.
S / 2 (and if S is odd, partitioning is immediately impossible)
B.
S / 4
C.
S - 1
D.
2 * S
Explanation & Key
Correct Answer:
40
What is the difference between Substring and Subsequence in string dynamic programming?
A.
Substrings must be contiguous characters; subsequences can have gaps as long as relative character order is preserved
B.
Subsequences must be contiguous; substrings can have gaps
C.
They are identical concepts
D.
Substrings only contain vowels
Explanation & Key
Correct Answer:
41
In Tree DP (e.g. House Robber III or Max Path Sum), what tree traversal order is mandatory to compute DP states?
A.
Pre-order
B.
Post-order (bottom-up: compute leaves before resolving parents)
C.
In-order
D.
Breadth-First Search
Explanation & Key
Correct Answer:
42
What is the Knuth-Yao Quadrangle Inequality optimization in Dynamic Programming?
A.
An optimization that reduces 2D Interval DP time complexity from O(n^3) to O(n^2) by bounding optimal split points
B.
A matrix inversion formula
C.
A geometry collision algorithm
D.
A sorting algorithm for 4D vectors
Explanation & Key
Correct Answer:
43
In the Maximum Subarray Sum problem (Kadane's Algorithm), why is Kadane classified as a 1D Dynamic Programming algorithm?
A.
Because `currentMax[i] = max(nums[i], nums[i] + currentMax[i-1])` represents an optimal substructure with memoization collapsed to a single variable
B.
Because it uses a 2D table
C.
Because it runs in O(n log n) time
D.
Because it uses binary search
Explanation & Key
Correct Answer:
Question Palette
Answered
Current
Not Attempted
Wrong
