二维经典DP,一维就不写了

解题思路:先定义dp[i][j]:至第i个a和第j个b的最长子序列

写出转换方程 , 若序列a第i个值==序列b第j个值 : dp[i][j]=max(dp[i-1][j-1]+1,dp[i][j]) ,否则:dp[i][j]=max(dp[i-1][j],dp[i][j-1])

方便理解可以画一个图(表格),横向为第一个序列,纵向为第二个序列,依for循环顺序写入

注意事项:下列为了方便所以dp列表多创建一格

参考代码:

a=list(input())
b=list(input())

dp=[[0 for i in range(len(a)+1)]for j in range(len(b)+1)]

for i in range(len(a)):
    for j in range(len(b)):
        if(a[i]==b[j]):
            dp[i+1][j+1]=max(dp[i][j]+1,dp[i+1][j+1])
        else:
            dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])
print(dp[-1][-1])