动态规划求最长公共子

串（LCS）是一种常用的字符串匹配算法。在两个字符串中，找到最长公共子串。下面是动态规划算法的实现步骤：

1. 定义状态：设 $dp[i][j]$ 表示字符串 a 的前 i 个字符和字符串 b 的前 j 个字符的最长公共子串长度。

2. 状态转移方程：

- 当 $a[i] = b[j]$ 时，$dp[i][j] = dp[i-1][j-1]+1$；
- 当 $a[i] \neq b[j]$ 时，$dp[i][j] = 0$。

3. 初始化：$dp[0][j] = 0, dp[i][0] = 0$。

4. 最优解：最长公共子串的长度为 $\max\limits_{i,j}dp[i][j]$，并可以通过 $dp$ 数组反推出最长公共子串。

下面是代码实现（使用 Python 语言）：

def LCS(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n+1) for _ in range(m+1)]
    max_len, end = 0, 0
    for i in range(1, m+1):
        for j in range(1, n+1):
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
                if dp[i][j] > max_len:
                    max_len = dp[i][j]
                    end = i
            else:
                dp[i][j] = 0
    return a[end-max_len:end]

其中，$a$ 和 $b$ 分别是两个字符串。函数返回的是最长公共子串。