Q. In dynamic programming, what is the purpose of a state transition equation?
A.
To define the base case
B.
To describe how to move from one state to another
C.
To optimize the algorithm
D.
To sort the data
Solution
A state transition equation describes how to move from one state to another in the dynamic programming solution, defining the relationship between subproblems.
Correct Answer:
B
— To describe how to move from one state to another
Q. What is the space complexity of the dynamic programming solution for the Longest Common Subsequence problem?
A.
O(m + n)
B.
O(m * n)
C.
O(m)
D.
O(n)
Solution
The space complexity of the dynamic programming solution for the Longest Common Subsequence problem is O(m * n), where m and n are the lengths of the two sequences.
Q. Which dynamic programming technique builds the solution from the ground up?
A.
Top-down approach
B.
Bottom-up approach
C.
Recursive approach
D.
Iterative approach
Solution
The bottom-up approach builds the solution from the smallest subproblems up to the larger problem, ensuring all necessary subproblem solutions are available.
