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", s2 = "acez", their longest common subsequence is lcs = "ace" with a length of 3, so the algorithm returns 3.

If you haven't solved this problem before, the simplest brute-force algorithm is to list all subsequences of s1 and s2, then check if there are any common ones, and find the longest one among them.

Obviously, this approach has a very high complexity as you need to enumerate all subsequences, which results in exponential complexity and is certainly impractical.

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