蓝桥杯-最长公共子序列（线性dp）

没有白走的路，每一步都算数???

题目描述：

已知有两个数组a,b。已知每个数组的长度。要求求出两个数组的最长公共子序列

序列 1 2 3 4 5  序列 2 3 2 1 4 5

子序列：从其中抽掉某个或多个元素而产生的新序列。其中子序列可以和本身一样

这里1 2 3 4 5的子序列挺多,总共有这么多个

 同理 2 3 2 1 4 5的子序列也有很多，但是应该比下面的要少，因为出现重复的元素

公共子序列：即两个序列中共有的部分

长度为1的：1 2 3 4 5

部分长度为2的： 23 

部分长度为3的： 234

长度为4的：2345 

最长公共子序列：最长的公共子序列

2 3 4 5

输入描述：

第一行：

输入N，M表示两个数组的长度

第二行：

数组a中的元素

第三行：

数组b中的元素

输出描述：

输出两个数组的最长公共子序列的长度

样例输入输出：

样例输入:

5 6

1 2 3 4 5

2 3 2 1 4 5

样例输出：

4

算法分析：

import os
import sys
n,m = map(int,input().split())
a = [0]+[int(i) for i in input().split()]
b = [0]+[int(i) for i in input().split()]
dp = [[0]*(m+1) for i in range(n+1)]
for i in  range(1,n+1):
  for j in range(1,m+1):
    if a[i] == b[j]:
      dp[i][j] = dp[i-1][j-1]+1
    else:
      dp[i][j] = max(dp[i-1][j],dp[i][j-1])
print(dp[n][m])

每日一句

摘自《三体》：

生存在宇宙中，本身就是一件很幸运的事情，但是不知道什么时候起，你们有了这样一种幻想，认为生存是唾手可得的，这就是你们失败因的根本原。