最长公共子序列 蓝桥杯 1189

题目描述：给定一个长度为n数组A和一个长度为m数组B。请你求出它们的最长公共子序列长度为多少

输入描述：输入第一行包含两个整数n,m.第二行包含n个整数ai，第三行包含m个整数bi，1<=n,m<=10^3,1<=ai,bi<=10^9

输出描述：输出一行整数表示答案

思路：如果用暴力枚举的方式，当n和m长度大时，情况太多

所以想到了动态规划，不停更新dp数组

分两种情况

1.a[i]=b[i],这样的话dp[i][j]=dp[i-1][j-1]+1

2.a[i]!=b[i],这样的话dp[i][j]=max(dp[i-1][j],dp[i][j-1])

n,m=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
# 初始化一个二维数组，行数为n的大小，列数为m的大小
res = [[0 for i in range(m + 1)] for j in range(n + 1)]
for i in range(1, n+1):
    for j in range(1, m+1):
        if a[i - 1] == b[j - 1]:
            res[i][j] = 1 + res[i - 1][j - 1]
        else:
            res[i][j] = max(res[i][j-1],res[i-1][j])

print(res[-1][-1])

最长公共子序列和最长公共子串的区别是，公共子序列可以不连续，公共子串必须连续，如果本题改为求最长公共子串则需要用一个maxres记录最长公共子串的值

n,m=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
# 初始化一个二维数组，行数为n的大小，列数为m的大小
res = [[0 for i in range(m + 1)] for j in range(n + 1)]
maxres=0
for i in range(1, n+1):
    for j in range(1, m+1):
        if a[i - 1] == b[j - 1]:
            res[i][j] = 1 + res[i - 1][j - 1]
        else:
            res[i][j] = 0
        maxres = max(res[i][j],maxres)

print(maxres)