为了分析卸载用户公共行为，发现初级的解法并不能满足时间复杂度。
动态规划求解矩阵：
def dp_loopkup(lx, ly, lookup):
for i in range(1, lx + 1):
for j in range(1, ly + 1):
if X[i - 1] == Y[j - 1]:
lookup[i][j] = lookup[i - 1][j - 1] + 1
else:
lookup[i][j] = max(lookup[i - 1][j], lookup[i][j - 1])
初级递归解法：
def findLCS(X, Y):
lx = len(X)
ly = len(Y)
lookup = [[0 for x in range(ly + 1)] for y in range(lx + 1)]
dp_loopkup(lx, ly, lookup)
def LCS(m, n):
if m == 0 or n == 0:
return {()}
if X[m - 1] == Y[n - 1]:
lcs = LCS(m - 1, n - 1)
return {(*l, X[m - 1]) for l in lcs}
if lookup[m - 1][n] > lookup[m][n - 1]:
return LCS(m - 1, n)
if lookup[m][n - 1] > lookup[m - 1][n]:
return LCS(m, n - 1)
top = LCS(m - 1, n, )
left = LCS(m, n - 1)
return top.union(left)
r = LCS(lx, ly)
return r
发现不对劲，长度大一点，算不出来。简单分析一下，加一个缓存。(常规操作)
def findLCS(X, Y):
lx = len(X)
ly = len(Y)
lookup = [[0 for x in range(ly + 1)] for y in range(lx + 1)]
dp_loopkup(lx, ly, lookup)
@lru_cache()
def LCS(m, n):
if m == 0 or n == 0:
return {()}
if X[m - 1] == Y[n - 1]:
lcs = LCS(m - 1, n - 1)
return {(*l, X[m - 1]) for l in lcs}
if lookup[m - 1][n] > lookup[m][n - 1]:
return LCS(m - 1, n)
if lookup[m][n - 1] > lookup[m - 1][n]:
return LCS(m, n - 1)
top = LCS(m - 1, n, )
left = LCS(m, n - 1)
return top.union(left)
r = LCS(lx, ly)
return r
长度再一大发现： RecursionError: maximum recursion depth exceeded in comparison
不想动 python 只好转迭代。转迭代通用的技巧就是使用栈。
但具体问题怎么求解，其实并不是那么直观。反复试错得到：
def findLCS_iter(X, Y):
lx = len(X)
ly = len(Y)
lookup = [[0 for x in range(ly + 1)] for y in range(lx + 1)]
dp_loopkup(lx, ly, lookup)
def LCS(lm, ln):
range_queue = deque()
result = set()
range_queue.append((lm, ln, ()))
while len(range_queue) > 0:
m, n, common = range_queue.pop()
if m == 0 or n == 0:
result.add(common)
continue
if X[m - 1] == Y[n - 1]:
range_queue.append((m - 1, n - 1, (X[m - 1], *common)))
continue
if lookup[m - 1][n] > lookup[m][n - 1]:
range_queue.append((m - 1, n, common))
continue
if lookup[m][n - 1] > lookup[m - 1][n]:
range_queue.append((m, n - 1, common))
continue
range_queue.append((m - 1, n, common))
range_queue.append((m, n - 1, common))
return result
return LCS(lx, ly)
到这一步其实已经满足需求了至少可以求解了。
还是发现有点慢。只好再做一次 cache 了。
def findLCS_iter(X, Y):
lx = len(X)
ly = len(Y)
lookup = [[0 for x in range(ly + 1)] for y in range(lx + 1)]
dp_loopkup(lx, ly, lookup)
class RememberDeque(deque):
def __init__(self):
self.rember = set()
super().__init__()
def append(self, x):
if x not in self.rember:
self.rember.add(x)
super().append(x)
def LCS(lm, ln):
range_queue = RememberDeque()
result = set()
range_queue.append((lm, ln, ()))
while len(range_queue) > 0:
m, n, common = range_queue.pop()
if m == 0 or n == 0:
result.add(common)
continue
if X[m - 1] == Y[n - 1]:
range_queue.append((m - 1, n - 1, (X[m - 1], *common)))
continue
if lookup[m - 1][n] > lookup[m][n - 1]:
range_queue.append((m - 1, n, common))
continue
if lookup[m][n - 1] > lookup[m - 1][n]:
range_queue.append((m, n - 1, common))
continue
range_queue.append((m - 1, n, common))
range_queue.append((m, n - 1, common))
return result
到此为止，我的认知上就只能这样了。
是否还有更好的方案呢？
更好的数据结构？
deque 和 cache 结合？
或者是其他什么约束条件，某些元组不用放入栈里？