蓝桥杯算法提高VIP-最长公共子序列-动态规划

解题思路:
例如:

ABC

BCD

思维：

if 两个字符串相等 

    if 行或列为第0排

        该空格为1

    else

        该空格为左上角的数加一

else

    该空格为 上方与左方的最大值

填表：

注意事项:

参考代码:

s1 = input()
s2 = input()
dp = [[0 for _ in range(len(s2))] for __ in range(len(s1))]
# print(dp)
for i in range(len(s1)):
    for j in range(len(s2)):
        if s1[i] == s2[j]:
            if i == 0 or j == 0:
                dp[i][j] = 1
            else:
                dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j],dp[i][j-1])
print(dp[-1][-1])