Answer: Zoho OA Question 2024 September | Dynamic Programming | on-campus

Solution: Longest Common Subsequence — 2D Bottom-Up DP Approach We use 2D Bottom-Up Dynamic Programming. Define dp[i][j] as the length of the longest common subsequence of text1[0..i-1] and text2[0..j-1]. The recurrence relation is: If text1[i-1] == text2[j-1]: the characters match, so dp[i][j] = dp[i-1][j-1] + 1. Otherwise: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) — take the best result from skipping one character of either string. The base case is dp[0][j] = 0 and dp[i][0] = 0 (empty string has LCS of 0 ...