Q. What is the main difference between dynamic programming and divide and conquer?
A.
Dynamic programming solves problems by breaking them into independent subproblems
B.
Divide and conquer uses memoization
C.
Dynamic programming solves problems with overlapping subproblems
D.
There is no difference
Solution
The main difference is that dynamic programming is used for problems with overlapping subproblems, while divide and conquer is used for problems that can be broken into independent subproblems.
Correct Answer:
C
— Dynamic programming solves problems with overlapping subproblems
Q. What is the space complexity of the dynamic programming solution for the 0/1 Knapsack problem?
A.
O(1)
B.
O(n)
C.
O(w)
D.
O(n*w)
Solution
The space complexity of the dynamic programming solution for the 0/1 Knapsack problem is O(n*w), where n is the number of items and w is the maximum weight capacity.
Q. What is the time complexity of the longest common subsequence problem using dynamic programming?
A.
O(n)
B.
O(m)
C.
O(n*m)
D.
O(n^2)
Solution
The longest common subsequence problem can be solved using a dynamic programming approach with a time complexity of O(n*m), where n and m are the lengths of the two sequences.
