1. 最长公共子序列（LCS）
1.1 问题描述
1.2 思路
利用动态规划。
下一步就要找到状态之间的转换方程。
因此可以根据这个方程来进行填表，以"helloworld"和“loop”为例：
1.3 Python代码
def
LCS
(
string1
,
string2
)
:
len1
=
len
(
string1
)
len2
=
len
(
string2
)
res
=
[
[
0
for
i
in
range
(
len1
+
1
)
]
for
j
in
range
(
len2
+
1
)
]
for
i
in
range
(
1
,
len2
+
1
)
:
for
j
in
range
(
1
,
len1
+
1
)
:
if
string2
[
i
-
1
]
==
string1
[
j
-
1
]
:
res
[
i
]
[
j
]
=
res
[
i
-
1
]
[
j
-
1
]
+
1
else
:
res
[
i
]
[
j
]
=
max
(
res
[
i
-
1
]
[
j
]
,
res
[
i
]
[
j
-
1
]
)
return
res
,
res
[
-
1
]
[
-
1
]
print
(
LCS
(
"helloworld"
,
"loop"
)
)
# 输出结果为：
[
[
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
]
,
[
0
,
0
,
0
,
1
,
1
,
1
,
1
,
1
,
1
,
1
,
1
]
,
[
0
,
0
,
0
,
1
,
1
,
2
,
2
,
2
,
2
,
2
,
2
]
,
[
0
,
0
,
0
,
1
,
1
,
2
,
2
,
3
,
3
,
3
,
3
]
,
[
0
,
0
,
0
,
1
,
1
,
2
,
2
,
3
,
3
,
3
,
3
]
]
,
3
所以"helloworld"和"loop"的最长公共子序列的长度为3。
1.4 找到具体的子序列
下面的内容借鉴了博主Running07的博客动态规划 最长公共子序列 过程图解
如果有两个字符串如下：
S1 = “123456778”
S2 = “357486782”
其最终的动态规划填表结果为：
其中S1和S2的LCS并不是只有1个。
我们根据递归公式：
构建了上表，
通过递推公式，可以看出，res[i][j]的值来源于res[i-1][j]或者是res[i-1][j]和res[i][j-1]的较大值（
可能相等
）。
我们将从最后一个元素c[8][9]倒推出S1和S2的LCS。
res[8][9] = 5，且S1[8] != S2[9]，所以倒推回去，res[8][9]的值来源于c[8][8]的值(因为res[8][8] > res[7][9])。
res[8][8] = 5, 且S1[8] = S2[8], 所以倒推回去，res[8][8]的值来源于 res[7][7]。
以此类推，如果遇到S1[i] != S2[j] ，且res[i-1][j] = res[i][j-1] 这种存在分支的情况，这里都选择一个方向（之后遇到这样的情况，也选择相同的方向，要么都往左，要么都往上）。
可得S1和S2的LCS为{3、5、7、7、8}
这是遇见相等的时候，统一往左走
S1和S2之间还有一个LCS
这是遇见相等的时候，统一往上走
：
可得S1和S2的LCS为{3、4、6、7、8}
2. 最长公共子串
2.1 问题描述
2.2 思路
和最长公共子序列一样，使用动态规划的算法。
下一步就要找到状态之间的转换方程。
和LCS问题唯一不同的地方在于当A[i] != B[j]时，res[i][j]就直接等于0了，因为子串必须连续，
且res[i][j] 表示的是以A[i]，B[j]截尾的公共子串的长度
。因此可以根据这个方程来进行填表，以"helloworld"和“loop”为例：
这个和LCS问题还有一点不同的就是，需要设置一个res，每一步都更新得到最长公共子串的长度。
2.3 Python代码
def
LCstring
(
string1
,
string2
)
:
len1
=
len
(
string1
)
len2
=
len
(
string2
)
res
=
[
[
0
for
i
in
range
(
len1
+
1
)
]
for
j
in
range
(
len2
+
1
)
]
result
=
0
for
i
in
range
(
1
,
len2
+
1
)
:
for
j
in
range
(
1
,
len1
+
1
)
:
if
string2
[
i
-
1
]
==
string1
[
j
-
1
]
:
res
[
i
]
[
j
]
=
res
[
i
-
1
]
[
j
-
1
]
+
1
result
=
max
(
result
,
res
[
i
]
[
j
]
)
return
result
print
(
LCstring
(
"helloworld"
,
"loop"
)
)
# 输出结果为：2
