Q. In the dynamic programming solution for the longest common subsequence, what does the dp[i][j] cell represent?
A.
Length of LCS for first i characters of string A and first j characters of string B
B.
Total number of subsequences
C.
Characters in the LCS
D.
Length of the strings A and B
Solution
The dp[i][j] cell in the longest common subsequence problem represents the length of the LCS for the first i characters of string A and the first j characters of string B.
Correct Answer:
A
— Length of LCS for first i characters of string A and first j characters of string B
Q. What is the optimal substructure property in dynamic programming?
A.
The problem can be divided into smaller subproblems
B.
The solution can be constructed from optimal solutions of its subproblems
C.
The problem has overlapping subproblems
D.
All of the above
Solution
The optimal substructure property in dynamic programming means that the solution can be constructed from optimal solutions of its subproblems, and the problem can be divided into smaller subproblems.
