Q. In the 0/1 Knapsack problem, what does the '0/1' signify?
A.
Items can be divided
B.
Items can be taken or left
C.
Items can be taken multiple times
D.
Items have no weight
Solution
The '0/1' in the 0/1 Knapsack problem signifies that each item can either be taken (1) or left (0), meaning items cannot be divided or taken multiple times.
Q. What is the main characteristic of problems that can be solved using dynamic programming?
A.
Optimal substructure
B.
Greedy choice property
C.
Linear time complexity
D.
Constant space complexity
Solution
The main characteristic of problems that can be solved using dynamic programming is the optimal substructure, meaning that the optimal solution can be constructed from optimal solutions of its subproblems.
Q. What is the space complexity of the dynamic programming solution for the Fibonacci sequence?
A.
O(1)
B.
O(n)
C.
O(n^2)
D.
O(log n)
Solution
The space complexity of the dynamic programming solution for the Fibonacci sequence can be optimized to O(1) by storing only the last two computed values.
Q. Which dynamic programming technique is used to solve the problem of finding the minimum edit distance between two strings?
A.
Memoization
B.
Tabulation
C.
Greedy
D.
Backtracking
Solution
The minimum edit distance problem is typically solved using the tabulation technique of dynamic programming, where a table is filled based on the edit operations.
