题解 | python 15行递推填表动态规划解法

while True:
    try:
        a, b = input(), input()
    except:
        break
    else:
        max_len = 0
        c = [[0 for i in range(len(b) + 1)] for j in range(len(a) + 1)]  # i=0和j=0时为哨兵元素
        for i in range(1, len(a) + 1):  # 递推填表
            for j in range(1, len(b) + 1):
                if a[i - 1] == b[j - 1]:  # 由于哨兵的增加，注意字符串的索引
                    c[i][j] = c[i - 1][j - 1] + 1
                    if max_len < c[i][j]:
                        max_len = c[i][j]
        print(max_len)

思路的话，正好以前上算法导论时写过这个作业，就直接把作业截图放这里了：