Dynamic Programming: Solving the Longest Common Subsequence Problem

The Longest Common Subsequence (LCS) problem asks for finding the longest subsequence that is common to two given sequences. A subsequence of a string is a sequence derived from the original string by deleting some or no characters without changing the order of the remaining characters.

To solve this problem using dynamic programming, we can use a 2D array to store lengths of longest common suffixes of substrings. The idea is:

• Initialize a 2D table `dp` where `dp[i][j]` will hold the length of LCS of strings `X[0..i-1]` and `Y[0..j-1]`.
• If characters `X[i-1]` and `Y[j-1]` match, then `dp[i][j] = dp[i-1][j-1] + 1`.
• Otherwise, `dp[i][j] = max(dp[i-1][j], dp[i][j-1])`. This means the LCS is either excluding the last character of `X` or `Y`, whichever results in a longer LCS.

def longest_common_subsequence(X, Y):
	m, n = len(X), len(Y)
	dp = [[0] * (n + 1) for _ in range(m + 1)]

	for i in range(1, m + 1):
		for j in range(1, n + 1):
			if X[i-1] == Y[j-1]:
				dp[i][j] = dp[i-1][j-1] + 1
		else:
			dp[i][j] = max(dp[i-1][j], dp[i][j-1])

	# The length of the longest common subsequence is in dp[m][n]
	return dp[m][n]

The time complexity of this dynamic programming solution is O(m * n), where m and n are the lengths of the two input strings. This is because we need to fill an m x n table, where each cell requires constant time to compute.

Space complexity is also O(m * n) due to the 2D array used to store intermediate results. However, this can be optimized to O(n) by using only two arrays of size n, as we only need the current row and the previous row to calculate the current row.