动态规划求解最长公共子序列， Python 实现的过程中遇到的问题

[zeroday]

看网络课程中用动态规划求解最大公共子序列，老师讲了原理，我准备用 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)

[hahastudio]

递归版本的问题在于 max 上面，你直接比较了两个字符串，它们应该是按字典序比较的，而这里你需要按长度比较，加一个参数 key=len
DP 版本没细看，估计也是这个问题

其实这样的经典问题，都有常见样例，比如：
http://rosettacode.org/wiki/Longest_common_subsequence#Recursion_7

[zeroday]

@hahastudio 非常感谢你的帮助解答，这个网站真不错。