What is the Longest Common Subsequence problem, and how can it be solved using dynamic programming?

The Longest Common Subsequence (LCS) problem is a classic computer science problem that involves finding the longest subsequence that is common to two given sequences. A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. For example, the LCS of the sequences "ABCDGH" and "AEDFHR" is "ADH", with a length of 3.

Dynamic programming can be used to solve the LCS problem efficiently by breaking it down into smaller subproblems and solving them independently. The basic idea is to construct a table that represents the lengths of the LCSs for all possible pairs of prefixes of the two sequences, and then use this table to compute the length of the LCS for the entire sequences.

Here is an example implementation of the LCS problem using dynamic programming in Java:

public class LCS {
    public int lcs(char[] X, char[] Y, int m, int n) {
        int[][] table = new int[m+1][n+1];
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i == 0 || j == 0) {
                    table[i][j] = 0;
                } else if (X[i-1] == Y[j-1]) {
                    table[i][j] = 1 + table[i-1][j-1];
                } else {
                    table[i][j] = Math.max(table[i-1][j], table[i][j-1]);
                }
            }
        }
        return table[m][n];
    }
}

In this implementation, the lcs method takes as input two character arrays X and Y, and their lengths m and n, respectively. It initializes a table of size (m+1) x (n+1) to store the lengths of the LCSs for all possible pairs of prefixes of X and Y. It then iterates through the table, computing the lengths of the LCSs for each pair of prefixes based on the lengths of their smaller prefixes. The length of the LCS for the entire sequences is then found in the bottom-right corner of the table.

The time complexity of the LCS problem using dynamic programming is O(mn), where m and n are the lengths of the input sequences. This is significantly more efficient than the brute-force approach, which has a time complexity of O(2ⁿ).