Classic DP: Longest Common Subsequence

I don't know how you feel about solving algorithm problems, but I've summarized the technique: break down a large problem into a single point, first study how to solve the problem at this small point, and then expand it to the entire problem through recursion/iteration.

For example, in our previous article Hand-Holding Guide to Binary Trees - Part 3, when solving binary tree problems, we break down the entire problem to a single node. Imagine standing at that node, think about what needs to be done, and then apply the binary tree recursion framework.

The same goes for dynamic programming problems, especially those related to subsequences. This article starts with the 'Longest Common Subsequence' problem and summarizes three subsequence problems, explaining the pattern for these subsequence problems in detail. You'll get a feel for this way of thinking.

Longest Common Subsequence

Calculating the Longest Common Subsequence (LCS) is a classic dynamic programming problem. LeetCode problem #1143 'Longest Common Subsequence' is about this:

Given two input strings s1 and s2, find their longest common subsequence and return the length of this subsequence. The function signature is as follows:

int longestCommonSubsequence(String s1, String s2);

int longestCommonSubsequence(string s1, string s2);

def longestCommonSubsequence(s1: str, s2: str) -> int:

func longestCommonSubsequence(s1 string, s2 string) int {
}

var longestCommonSubsequence = function(s1, s2) {
};

For example, given s1 = "zabcde" and s2 = "acez", their longest common subsequence is lcs = "ace", with a length of 3, so the algorithm returns 3.

If you haven't encountered this problem before, the simplest brute-force approach would be to enumerate all subsequences of s1 and s2, then check for common subsequences, and finally find the one with the maximum length among them.

Clearly, this approach has a very high complexity. Enumerating all subsequences has an exponential complexity, which is impractical.

The correct approach is not to consider the entire strings, but to focus on each character of s1 and s2. A pattern summarized in the previous article Subsequence Problem Template is: