AcWing 272. 最长公共上升子序列(Python)
原题链接
中等
作者:
今天AC了吗
,
2022-02-25 11:09:22
,
所有人可见
,
阅读 281
最长公共上升子序列
算法分析
- 定义dp数组:
dp[i][j]
表示第一个序列的前i个元素与第二个序列前j个字母以b[j]
结尾的最长公共上升子序列长度
- dp递推式:如果不选
a[i]
元素,最长公共上升子序列长度为dp[i-1][j]
;如果选a[i]
元素,在a[i] == b[j]
的前提,内部按照以b[1]~b[j-1]
结尾的上升子序列划分。表达式为dp[i][j]=max(dp[i-1][1]+1,dp[i-1][2]+1,...dp[i-1][j-1]+1)
朴素算法:时间复杂度 $O(n^3)$
Python 代码
n = int(input())
a = [0] + list(map(int,input().split()))
b = [0] + list(map(int,input().split()))
dp =[[0 for i in range(n+1)]for j in range(n+1)]
for i in range(1,n+1):
for j in range(1,n+1):
dp[i][j] = dp[i-1][j] #不选a[i]元素
if a[i] == b[j]: #选择a[i]元素
dp[i][j] = 1
for k in range(1,j):
if b[k] < b[j]:
dp[i][j] = max(dp[i][j], dp[i-1][k]+1)
ans = 0
for i in range(1,n+1):
ans = max(ans, dp[n][i])
print(ans)
优化:
因为每次转移都需要从前缀的状态转移过来,所以可以用一个变量maxv
来储存当前a[i] > b[k]
时dp[i-1][k]+1的最大值
将复杂度降为二维。
时间复杂度 $O(n^2)$
Python 代码
n = int(input())
a = [0] + list(map(int,input().split()))
b = [0] + list(map(int,input().split()))
dp =[[0 for i in range(n+1)]for j in range(n+1)]
for i in range(1,n+1):
maxv = 1 #用maxv记录最长的长度
for j in range(1,n+1):
dp[i][j] = dp[i-1][j] #不选a[i]元素
if a[i] == b[j]: #选择a[i]元素
dp[i][j] = max(dp[i][j], maxv)
if a[i] > b[j]:
maxv = max(maxv, dp[i-1][j]+1)
ans = 0
for i in range(1,n+1):
ans = max(ans, dp[n][i])
print(ans)