优化前:
# f[i][j]集合表示的是a中的前i个数和b中前j个数中的公共上升子序列。
# 其中a[i]不一定包含在内,但是b[j]一定包含在内
# 所以大体上可以分为两类,即包含a[i]和不包含a[i]
# 当包含a[i]时,即a[i]=b[j](此时才是正真dp的开始)
n = int(input())
a, b = [], []
a.extend([0]+list(map(int, input().split())))
b.extend([0]+list(map(int, input().split())))
f = [[0]*(n+1) for _ in range(n+1)]
for i in range(1, n + 1):
for j in range(1, n + 1):
# 不包含a[i]时
f[i][j] = f[i-1][j]
# 包含a[i]时
if a[i] == b[j]:
f[i][j] = max(f[i][j], 1)
# f[i-1][k]表示的是f[i][j]前面的集合
for k in range(1, j):
if b[k] < b[j]:
f[i][j] = max(f[i][j], f[i-1][k] + 1)
# 直接对a数组取a[n],这样只要枚举b数组
ans = 0
for i in range(1, n+1):
ans = max(ans, f[n][i])
print(ans)
优化后:
n = int(input())
a, b = [], []
a.extend([0]+list(map(int, input().split())))
b.extend([0]+list(map(int, input().split())))
f = [[0]*(n+1) for _ in range(n+1)]
for i in range(1, n + 1):
maxv = 1
for j in range(1, n + 1):
f[i][j] = f[i-1][j]
if a[i] == b[j]:
f[i][j] = max(f[i][j], maxv)
if b[j] < a[i]:
# maxv存储的是f[i][j]之前的最大值
maxv = max(maxv, f[i-1][j] + 1)
ans = 0
for i in range(1, n+1):
ans = max(ans, f[n][i])
print(ans)