Dynamic Programming MCQs in C
Basic DP Concepts (30 Questions)
1. What is the main principle behind Dynamic Programming?
A) Divide and conquer
B) Breaking problems into overlapping subproblems
C) Using greedy choices
D) Random selection
Answer: B) Breaking problems into overlapping subproblems
DP solves problems by breaking them into overlapping subproblems and storing their solutions.
2. Which of these is NOT a characteristic of DP problems?
A) Optimal substructure
B) Overlapping subproblems
C) Greedy choice property
D) Memoization
Answer: C) Greedy choice property
Greedy choice property is specific to greedy algorithms, not DP.
3. What is memoization in DP?
A) Storing intermediate results to avoid recomputation
B) Writing down the problem statement
C) Breaking problems into smaller parts
D) Using minimum memory
Answer: A) Storing intermediate results to avoid recomputation
Memoization stores previously computed results to improve efficiency.
4. Which approach typically uses more memory?
A) Top-down DP with memoization
B) Bottom-up DP
C) Both use same memory
D) Depends on implementation
Answer: D) Depends on implementation
Both approaches can be implemented with similar memory usage.
5. What is the time complexity of the DP solution for Fibonacci numbers?
A) O(1)
B) O(n)
C) O(n²)
D) O(2ⁿ)
Answer: B) O(n)
DP reduces Fibonacci from exponential to linear time.
6. Which problem is NOT typically solved with DP?
A) Fibonacci numbers
B) Knapsack problem
C) Merge sort
D) Longest common subsequence
Answer: C) Merge sort
Merge sort uses divide and conquer without overlapping subproblems.
7. What is optimal substructure in DP?
A) Problem can be divided into independent subproblems
B) Optimal solution can be constructed from optimal solutions of subproblems
C) Problem has a unique optimal solution
D) All subproblems must be solved optimally
Answer: B) Optimal solution can be constructed from optimal solutions of subproblems
Optimal substructure is a key property of DP problems.
8. Which of these is a classic DP problem?
A) Binary search
B) Quick sort
C) 0/1 Knapsack
D) Bubble sort
Answer: C) 0/1 Knapsack
0/1 Knapsack is a classic DP problem with overlapping subproblems.
9. What is the main advantage of bottom-up DP over top-down?
A) Easier to implement
B) Avoids recursion stack overhead
C) More intuitive
D) Always faster
Answer: B) Avoids recursion stack overhead
Bottom-up DP is iterative and avoids recursion stack limitations.
10. What data structure is commonly used for memoization?
A) Array
B) Hash table
C) Linked list
D) Both A and B
Answer: D) Both A and B
Arrays are common for integer parameters, hash tables for more complex states.
11. What is the space complexity of the DP solution for Fibonacci?
A) O(1)
B) O(n)
C) O(log n)
D) O(n²)
Answer: B) O(n)
Standard DP solution uses O(n) space for storing all Fibonacci numbers up to n.
12. Which technique is NOT used in DP?
A) Memoization
B) Tabulation
C) Backtracking
D) State transition
Answer: C) Backtracking
Backtracking is a different algorithmic technique.
13. What is the time complexity of the 0/1 Knapsack DP solution?
A) O(n)
B) O(n log n)
C) O(nW)
D) O(2ⁿ)
Answer: C) O(nW)
Where n is number of items and W is knapsack capacity.
14. Which problem demonstrates overlapping subproblems?
A) Calculating Fibonacci numbers
B) Binary search
C) Matrix multiplication
D) All of the above
Answer: A) Calculating Fibonacci numbers
Fibonacci calculations repeat the same subproblems many times.
15. What is the key difference between DP and divide-and-conquer?
A) DP uses recursion
B) DP has overlapping subproblems
C) Divide-and-conquer is faster
D) No difference
Answer: B) DP has overlapping subproblems
Divide-and-conquer problems have independent subproblems.
16. Which of these is a 1D DP problem?
A) Fibonacci numbers
B) Longest common subsequence
C) Matrix chain multiplication
D) All of the above
Answer: A) Fibonacci numbers
Fibonacci can be solved with a 1D array, others typically require 2D.
17. What is the recurrence relation for Fibonacci numbers?
A) fib(n) = fib(n-1) + fib(n-2)
B) fib(n) = fib(n-1) * fib(n-2)
C) fib(n) = fib(n-1) + n
D) fib(n) = fib(n/2) + fib(n/2-1)
Answer: A) fib(n) = fib(n-1) + fib(n-2)
Each Fibonacci number is the sum of the two preceding ones.
18. What is the space-optimized version of Fibonacci DP?
A) O(1) space
B) O(n) space
C) O(log n) space
D) O(n²) space
Answer: A) O(1) space
We only need to store the last two numbers to compute the next one.
19. What is the time complexity of the recursive Fibonacci without DP?
A) O(n)
B) O(n²)
C) O(2ⁿ)
D) O(log n)
Answer: C) O(2ⁿ)
Recursive Fibonacci without memoization has exponential time complexity.
20. Which problem is best solved with DP?
A) Finding the maximum element in an array
B) Calculating factorial of a number
C) Longest increasing subsequence
D) Reversing a string
Answer: C) Longest increasing subsequence
LIS has overlapping subproblems and optimal substructure.
21. What is the key idea behind DP optimization?
A) Solve each subproblem only once
B) Solve all possible subproblems
C) Guess the solution
D) Use brute force
Answer: A) Solve each subproblem only once
DP avoids recomputation by storing solutions to subproblems.
22. Which of these is a DP problem with a 2D state?
A) Fibonacci numbers
B) Longest common subsequence
C) Coin change problem
D) All of the above
Answer: B) Longest common subsequence
LCS typically uses a 2D DP table comparing two sequences.
23. What is the recurrence for the coin change problem?
A) dp[i] = min(dp[i], dp[i-coin] + 1)
B) dp[i] = dp[i-1] + dp[i-2]
C) dp[i] = max(dp[i], dp[i-coin])
D) dp[i] = dp[i] + dp[i-coin]
Answer: A) dp[i] = min(dp[i], dp[i-coin] + 1)
For each amount i, we consider using each coin denomination.
24. What is the space complexity of the LCS DP solution?
A) O(1)
B) O(n)
C) O(n²)
D) O(2ⁿ)
Answer: C) O(n²)
LCS typically uses a 2D table of size m×n where m,n are string lengths.
25. Which technique can reduce space complexity in DP?
A) Using bitmasking
B) Using only necessary rows
C) Using recursion
D) Both A and B
Answer: D) Both A and B
Various techniques can optimize DP space usage.
26. What is the time complexity of the DP solution for LCS?
A) O(n)
B) O(n log n)
C) O(n²)
D) O(2ⁿ)
Answer: C) O(n²)
LCS fills an n×n table with constant time per cell.
27. Which problem has a DP solution with O(n) space complexity?
A) Fibonacci numbers
B) Longest common subsequence
C) Matrix chain multiplication
D) All of the above
Answer: A) Fibonacci numbers
Fibonacci can be solved with O(n) space (or even O(1) with optimization).
28. What is the key difference between DP and greedy algorithms?
A) DP always finds optimal solution
B) Greedy makes locally optimal choices
C) DP considers all possibilities
D) All of the above
Answer: D) All of the above
These are key differences between DP and greedy approaches.
29. Which problem can be solved with both DP and greedy approaches?
A) Fibonacci numbers
B) Activity selection
C) 0/1 Knapsack
D) Longest common subsequence
Answer: B) Activity selection
Activity selection has a greedy solution, others typically require DP.
30. What is the optimal substructure property?
A) Problem can be divided into independent subproblems
B) Optimal solution can be constructed from optimal solutions of subproblems
C) Problem has a unique optimal solution
D) All subproblems must be solved optimally
Answer: B) Optimal solution can be constructed from optimal solutions of subproblems
This property allows DP to work by building up solutions.
Advanced DP Problems (20 Questions)
1. What is the time complexity of the DP solution for the matrix chain multiplication problem?
A) O(n)
B) O(n²)
C) O(n³)
D) O(2ⁿ)
Answer: C) O(n³)
The solution fills an n×n table with O(n) time per cell.
2. Which problem involves finding the minimum number of operations to convert one string to another?
A) Longest common subsequence
B) Edit distance
C) Knapsack problem
D) Matrix chain multiplication
Answer: B) Edit distance
Edit distance measures the minimum operations (insert, delete, replace) needed.
3. What is the recurrence relation for the edit distance problem?
A) dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
B) dp[i][j] = dp[i-1][j-1] if characters match
C) Both A and B
D) None of the above
Answer: C) Both A and B
The recurrence depends on whether the current characters match.
4. What is the time complexity of the DP solution for the subset sum problem?
A) O(n)
B) O(n log n)
C) O(nW)
D) O(2ⁿ)
Answer: C) O(nW)
Where n is number of elements and W is target sum (pseudo-polynomial).
5. Which problem involves finding the maximum value subset of items that fits a knapsack?
A) Coin change problem
B) 0/1 Knapsack problem
C) Activity selection problem
D) Longest path problem
Answer: B) 0/1 Knapsack problem
Classic DP problem with items having weights and values.
6. What is the recurrence relation for the 0/1 Knapsack problem?
A) dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt[i]] + val[i])
B) dp[i][w] = dp[i-1][w] + dp[i-1][w-wt[i]]
C) dp[i][w] = min(dp[i-1][w], dp[i-1][w-wt[i]])
D) dp[i][w] = dp[i][w] + val[i]
Answer: A) dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt[i]] + val[i])
We either include the current item or exclude it, taking the maximum value.
7. Which problem involves finding the longest sequence of numbers where each number is divisible by the previous one?
A) Longest increasing subsequence
B) Longest divisible subsequence
C) Longest common subsequence
D) Longest path in DAG
Answer: B) Longest divisible subsequence
Variation of LIS with divisibility condition.
8. What is the space complexity of the DP solution for the longest palindromic subsequence problem?
A) O(1)
B) O(n)
C) O(n²)
D) O(2ⁿ)
Answer: C) O(n²)
Requires a 2D table of size n×n where n is string length.
9. Which problem involves finding the minimum number of coins needed to make change?
A) Knapsack problem
B) Coin change problem
C) Subset sum problem
D) Partition problem
Answer: B) Coin change problem
Classic DP problem with unlimited coin supply.
10. What is the time complexity of the DP solution for the longest increasing subsequence problem?
A) O(n)
B) O(n log n)
C) O(n²)
D) O(2ⁿ)
Answer: C) O(n²)
Standard DP solution is O(n²), though O(n log n) solutions exist.
11. Which problem involves finding the minimum number of jumps to reach the end of an array?
A) Jump game
B) Staircase problem
C) Frog jump
D) All of the above
Answer: A) Jump game
Classic DP problem with array values representing maximum jump lengths.
12. What is the recurrence relation for the longest palindromic substring problem?
A) dp[i][j] = dp[i+1][j-1] && s[i] == s[j]
B) dp[i][j] = dp[i][j] + 1
C) dp[i][j] = max(dp[i+1][j], dp[i][j-1])
D) dp[i][j] = min(dp[i+1][j], dp[i][j-1])
Answer: A) dp[i][j] = dp[i+1][j-1] && s[i] == s[j]
A substring is palindromic if its inner substring is palindromic and ends match.
13. Which problem involves finding the maximum sum of non-adjacent elements?
A) Maximum subarray problem
B) House robber problem
C) Partition problem
D) Subset sum problem
Answer: B) House robber problem
Classic DP problem where you can't rob adjacent houses.
14. What is the recurrence relation for the house robber problem?
A) dp[i] = max(dp[i-1], dp[i-2] + nums[i])
B) dp[i] = dp[i-1] + dp[i-2]
C) dp[i] = max(dp[i-1], dp[i-2])
D) dp[i] = dp[i] + nums[i]
Answer: A) dp[i] = max(dp[i-1], dp[i-2] + nums[i])
At each house, we choose to rob it (skipping previous) or skip it.
15. Which problem involves finding the number of ways to climb stairs with 1 or 2 steps at a time?
A) Fibonacci sequence
B) Coin change problem
C) Staircase problem
D) Both A and C
Answer: D) Both A and C
The staircase problem follows the Fibonacci sequence pattern.
16. What is the time complexity of the DP solution for the word break problem?
A) O(n)
B) O(n²)
C) O(n³)
D) O(2ⁿ)
Answer: B) O(n²)
For each position, we check all possible prefixes against the dictionary.
17. Which problem involves finding the maximum profit in stock trading with at most one transaction?
A) Best time to buy and sell stock I
B) Best time to buy and sell stock II
C) Best time to buy and sell stock III
D) All of the above
Answer: A) Best time to buy and sell stock I
Version I allows only one transaction, others allow multiple.
18. What is the time complexity of the DP solution for the maximum subarray problem?
A) O(1)
B) O(n)
C) O(n log n)
D) O(n²)
Answer: B) O(n)
Kadane's algorithm provides an O(n) solution.
19. Which problem involves finding the minimum path sum from top to bottom of a triangle?
A) Minimum path sum
B) Triangle problem
C) Both A and B
D) None of the above
Answer: C) Both A and B
Commonly called the triangle problem or minimum path sum problem.
20. What is the space complexity of the DP solution for the unique paths problem (robot in grid)?
A) O(1)
B) O(n)
C) O(mn)
D) O(min(m,n))
Answer: D) O(min(m,n))
Can be optimized to use only a single row or column of storage.
Related DP Resources