📢 Too many exams? Don’t know which one suits you best? Book Your Free Expert 👉 call Now!

    Question

    Complete the recurrence relation for dp[i][j] in the

    Longest Common Subsequence (LCS) problem when text1[i-1] is *not equal* to text2[j-1]. # dp[i][j] stores the length of LCS for text1[:i] and text2[:j] if text1[i-1] == text2[j-1]:     dp[i][j] = 1 + dp[i-1][j-1] else:     dp[i][j] = _________ # Line to complete
    A dp[i-1][j-1] Correct Answer Incorrect Answer
    B max(dp[i-1][j], dp[i][j-1]) Correct Answer Incorrect Answer
    C min(dp[i-1][j], dp[i][j-1]) Correct Answer Incorrect Answer
    D dp[i-1][j] + dp[i][j-1] Correct Answer Incorrect Answer

    Solution

    • Code Analysis: o dp[i][j] stores the length of the LCS for text1[:i] and text2[:j]. o If text1[i-1] == text2[j-1] (the last characters match), we increment the LCS length from the previous subproblem (dp[i-1][j-1]). o If the characters do not match, we need to consider two possibilities: 1. The LCS of text1[:i-1] and text2[:j] (i.e., text1 without its last character). 2. The LCS of text1[:i] and text2[:j-1] (i.e., text2 without its last character). We take the maximum of these two options. • Explanation of Correct Answer (B): max(dp[i-1][j], dp[i][j-1]) o When text1[i-1] is not equal to text2[j-1], it means these characters cannot both be part of the LCS. Therefore, we must either exclude text1[i-1] and find the LCS of text1[:i-1] and text2[:j] (represented by dp[i-1][j]), or exclude text2[j-1] and find the LCS of text1[:i] and text2[:j-1] (represented by dp[i][j-1]). We choose the option that yields the longer LCS.

    Practice Next
    More IT Operating System Questions
    ask-question