最長共同子序列
1. (每次都超時，但要懂原理)遞歸方法
使用遞歸解決LCS問題，但效率較低。可以使用記憶化遞歸來提高效率。
python
def recursive_LCS(X, Y, m, n):
if m == 0 or n == 0:
return 0
if X[m - 1] == Y[n - 1]:
return 1 + recursive_LCS(X, Y, m - 1, n - 1)
else:
return max(recursive_LCS(X, Y, m, n - 1), recursive_LCS(X, Y, m - 1, n))2. 動態規劃方法
使用動態規劃解決LCS問題，通常使用二維數組。 求長度
python
dp = [[0] * (n + 1) for _ in range(m + 1)]
max_length = 0 # 記錄最長共同子字串的長度
# 填充 DP 表格
for i in range(1, m + 1):
for j in range(1, n + 1):
if str1[i-1] == str2[j-1]:
# 字符相同，延續之前的子字串
dp[i][j] = dp[i-1][j-1] + 1
max_length = max(max_length, dp[i][j])
else:
# 字符不同，子字串中斷
dp[i][j] = 0
return max_length求字串
python
def LCS_char(char, char2):
m = len(char)
n = len(char2)
dp = [[''] * (n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if char[i-1] == char2[j-1]:
dp[i][j] = dp[i-1][j-1] + char[i-1]
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1], key=lambda x: len(x))3. 滾動數組
優化動態規劃以減少空間覆雜度。
python
def rolling_LCS(X, Y):
m = len(X)
n = len(Y)
dp = [[0] * (n + 1) for _ in range(2)]
bi = 0 # 用於滾動的變量
for i in range(1, m + 1):
bi = i % 2 # 切換行
for j in range(1, n + 1):
if X[i - 1] == Y[j - 1]:
dp[bi][j] = dp[1 - bi][j - 1] + 1
else:
dp[bi][j] = max(dp[1 - bi][j], dp[bi][j - 1])
return dp[bi][n]4. 字符串編輯距離方法
使用編輯距離算法解決LCS問題。(最小編輯距離)
python
def MED(X, Y):
n = len(X)
m = len(Y)
dp = [[i+j for j in range(m+1)] for i in range(n+1)]
for i in range(1, n+1):
for j in range(1, m+1):
if X[i-1] == Y[j-1]:
d = 0
else:
d = 1
dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + d)
return dp[n][m]python
X = "ABCBDAB"
Y = "BDCAB"
print("recursive_LCS:", recursive_LCS(X, Y, len(X), len(Y)))
print("LCS:", LCS(X, Y))
print("rolling_LCS:", rolling_LCS(X, Y))
print("edit_distance_LCS:", MED(X, Y))Contributors
lucashsu95