字符串相关的动态题目非常多，我们选取其中最具代表性也是最常考的三个知识点

1、最长公共子串

问题描述：给出两个字符串，找到最长公共子串，并返回其长度。
输入: s = “ABCD”, t = “EABDF”
输出: 2
解释: s 和 t 的最长公共子串为 “AB”

题目解析：

2、最长公共子序列

问题描述：给出两个字符串，找到最长公共子序列(LCS)，返回LCS的长度。
输入: s = “ABCD”, t = “EABDF”
输出: 3
解释: s 和 t 的最长公共子序列为 “ABD”

题目解析：

3、字符串相似度/编辑距离

给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
输入: word1 = “horse”, word2 = “ros”
输出: 3
解释:
horse -> rorse (将’h’ 替换为 ‘r’)
rorse -> rose (删除 ‘r’) rose -> ros (删除 ‘e’)

题目解析：

掌握字符串相关的动态规划