Question

Consider the standard dynamic programming approach to find the length of the Longest Common Subsequence (LC

  • S of two strings, text1 and text2. The dp table is initialized with dimensions (len(text1) + 1) x (len(text2) + 1). Given text1 = "ABC" and text2 = "AXBY", what will be the value of dp[0][3] and dp[2][0] after the initialization and the first row/column filling steps of the following Python code? def lcs_length(text1, text2):     m = len(text1)     n = len(text2)     dp = [[0] * (n + 1) for _ in range(m + 1)]     # Initialization (first row and column are already 0 by default in Python list comprehension)     # for i in range(m + 1):     #     dp[i][0] = 0     # for j in range(n + 1):     #     dp[0][j] = 0     # Filling the DP table     for i in range(1, m + 1):         for j in range(1, n + 1):             if text1[i - 1] == text2[j - 1]:                 dp[i][j] = 1 + dp[i - 1][j - 1]             else:                 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])     return dp[m][n] # For this question, we only care about the state after initialization # and before the main loops start filling values beyond the first row/column. # The Python list comprehension [[0] * (n + 1) for _ in range(m + 1)] # already initializes all cells to 0.
A dp[0][3] = 0, dp[2][0] = 0
B dp[0][3] = 3, dp[2][0] = 2
C dp[0][3] = 0, dp[2][0] = 2
D dp[0][3] = 3, dp[2][0] = 0
Practice Next

Hey! Ask a query