Classic DP: Longest Common Subsequence

I'm not sure how everyone feels about solving algorithm problems, but I've concluded that the key is to break down a large problem into smaller parts. First, study how to solve a problem at a small scale, and then expand it to the entire problem using recursion/iteration.

For example, in our previous article Hands-on Tree Problems Part 3, we solved binary tree problems by focusing on a single node. Imagine yourself standing on a particular node, determine what needs to be done, and then apply the binary tree recursion framework.

The same applies to dynamic programming problems, especially those related to subsequences. This article expands from the "Longest Common Subsequence Problem" to summarize three subsequence problems. By carefully explaining how to solve this problem, you will grasp 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," addresses this issue:

Given two input strings, s1 and s2, find their longest common subsequence and return its length. 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: