这是一个创建于 3543 天前的主题，其中的信息可能已经有所发展或是发生改变。
看网络课程中用动态规划求解最大公共子序列，老师讲了原理，我准备用 Python 实现，实现过程中遇到一些问题，还请大家指教。
这是我的代码，第一个是递归解决，第二个是动态规划解决。
第一个递归版对于有点字符串结果正确，有点字符串结果不正确，请问是什么原因呢？比如两个字符串'didactical‘和’advantage', 可以得到正确的子序列'data', 而对于‘educational'和'advantage'得到的结果为'l'明显不正确。
第二个动态规划版没得出正确答案，不知道代码错在哪里，还请指点一下。
def lcs_recursive(str1, str2, str1_idx, str2_idx):
"""Computes longest common subsequence of str1 and str2 using recursive.
"""
if str1_idx == -1 or str2_idx == -1:
return ''
if str1[str1_idx] == str2[str2_idx]:
return lcs_recursive(str1, str2, str1_idx-1, str2_idx-1) + str1[str1_idx]
return max(lcs_recursive(str1, str2, str1_idx-1, str2_idx),
lcs_recursive(str1, str2, str1_idx, str2_idx-1))
def make_matrix(str1, str2):
"""Makes a matrix with given str1 and str2 to lcs problem."""
t = [[0 for col in range(len(str1))] for row in range(len(str2))]
for row in range(len(str2)-1):
for col in range(len(str1)-1):
if str1[col] == str2[row]:
t[row+1][col+1] = t[row][col] + 1
else:
t[row+1][col+1] = max(t[row][col+1], t[row+1][col])
return t
def print_lcs(t, str1, row, col):
"""Computes longest common subsequence of str1 and str2 using Dynamic programming.
"""
if row == -1 or col == -1:
return ''
if t[row][col] - 1 == t[row-1][col-1] and str1[col] == str2[row]:
print str1[col],
return print_lcs(t, str1, row-1, col-1)
if t[row][col] - 1 == t[row-1][col] and str1[col] == str2[row]:
print str1[col],
return print_lcs(t, str1, row-1, col)
if t[row][col] - 1 == t[row][col-1] and str1[col] == str2[row]:
print str1[col],
return print_lcs(t, str1, row, col-1)
if __name__ == '__main__':
str1 = 'didactical'
str2 = 'advantage'
str3 = 'educational'
t = make_matrix(str1, str2)
print '\n'.join(str(row) for row in t)
print lcs_recursive(str1, str2, len(str1)-1, len(str2)-1)
print lcs_recursive(str3, str2, len(str3)-1, len(str2)-1)
#print_lcs(t, str1, len(str2)-1, len(str1)-1)
 |
1
hahastudio 2015-03-16 17:37:36 +08:00  2
递归版本的问题在于 max 上面，你直接比较了两个字符串，它们应该是按字典序比较的，而这里你需要按长度比较，加一个参数 key=len
DP 版本没细看，估计也是这个问题 其实这样的经典问题，都有常见样例，比如： http://rosettacode.org/wiki/Longest_common_subsequence#Recursion_7 |
 |
2
zeroday OP @hahastudio 非常感谢你的帮助解答，这个网站真不错。
|
Select Language