# 经典动态规划：最长公共子序列

Info

**已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~**

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode | Difficulty |
---|---|

1143. Longest Common Subsequence | 🟠 |

583. Delete Operation for Two Strings | 🟠 |

712. Minimum ASCII Delete Sum for Two Strings | 🟠 |

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: