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

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)