字符串相关的动态规划最大公共子序列最大公共子串编辑距离
简述这三个算法解决的问题和展示状态转移方程并且给出可通过执行的Python代码。
最大公共子序列
子序列是,一个字符串中的任意字符组成的序列,重点在于,不要求子序列是原字符串的连续序列。
如下例子所示,acg是abcdefg的子序列,但不是连续子序列。
abcdefg ==> acg
两个字符串的最大公共子序列的状态转移方程式如下:
dp[i][j]={max{dp[i−1][j],dp[i][j−1]}if s1[i]!=s2[j]dp[i][j]+1if s1[i] =s2[j]dp[i][j]=
\begin{cases}
m