Now, let's look at a different problem which is solvable by a dynamic programming algorithm. The problem we're now interested in is the longest common subsequence problem.

We're interested in finding similarities between two given sequences by computing the Longest Common Subsequence (LCS) between them. A common subsequence, S₃, of two given sequences, S₁ and S₂, is a sequence whose elements appear in both S and S₂ in the same order, but not necessarily consecutively. This problem is usually applicable when finding DNA similarities of different organisms.

For example, if we have two strands, S₁ and S₂, as follows:

S₁ = ACCGGTCGAGTGCGCGGAGCCGGCCGAA
S₂ = GTCGTTCGGAATGCCGTTGCTCTGTAAAA

Then the longest common strand between those two, let's call it S₃, would be as follows:

S₃ = GTCGTCGGAAGCCGGCCGAA

This problem is solvable using dynamic programming. If we go for a brute force approach, we can enumerate all subsequences of S₁ and check each subsequence to see if it is also a subsequence of S₂, keeping track of the longest one we find.

However, if |S₁| = m, then S₁ has 2m subsequences, making it impractical for long sequences. The LCS exhibits the optimal-substructure property.

One way for this to become evident is to think in terms of prefixes. Let's assume that we have the following two sequences:

X = {x₁, x₂… x_m}
Y = {y₁, y₂… y_n}

Let Z be any LCS of X and Y that can be represented as follows:

Z = {z₁, z₂… z_k}

Then, the following cases are possible:

1. If x_m = y_n, then z_k = x_m = y_n, and therefore Z_k-1 is a LCS of X_m-1 and Y_n-1
2. If x_m != y_n, then z_k != x_m implies that Z is a LCS of X_m-1 and Y
3. If x_m != y_n, then z_k != y_n implies that Z is a LCS of X and Yn-1

This tells us that an LCS of two sequences contains the LCS of prefixes of the two sequences, exhibiting the optimal-substructure property. If we define c[i][j] to be the length of a LCS of sequences X_i and Y_j, then we can arrive at the following recursive formula, which guides us toward the dynamic programming solution for the problem that can be represented as follows:

Looking at the recurrence, the property of overlapping subproblems immediately pops out.

To find a LCS of X and Y, we may need to find the LCS's of X and Y_n-1 and X_m-1 and Y, but each of these have the problem of finding the LCS of X_m-1 and Y_n-1. Many other subproblems share sub-subproblems.

Using this recurrence, in a bottom-up fashion (where we have solutions for subproblems readily computed), we can produce the following dynamic programming algorithm to compute the length of the longest common subsequence of two strings:

public int length(String x, String y) {
  int m = x.length();
  int n = y.length();
  int[][] c = new int[m + 1][n + 1];
  for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
      if (x.charAt(i - 1) == y.charAt(j - 1))
        c[i][j] = c[i - 1][j - 1] + 1;
      else
        c[i][j] = Math.max(c[i - 1][j], c[i][j - 1]);
    }
  }
  return c[m][n];
}

It is possible to also compute the longest common subsequence, and not only the length of it if we keep track of the direction we go in the c matrix on each step (either up or left), taking into account that we only add a new character to the optimal subsequence when x_i = y_j.

We don't cover the solution to this problem in this book. If you are interested in it, the Wikipedia page for the LCS problem has a detailed walkthrough on the implementation of it: https://en.wikipedia.org/wiki/Longest_common_subsequence_problem.