蓝桥 python笔记12——动态规划、二维dp、最长上升子序列、最长公共子序列

目录

动态规划

二维dp

最长上升子序列

最长公共子序列

动态规划

# dp[n]表示n个台阶方案数
# dp[n]=dp[n-1]+dp[n-2]
# dp[1]=1   dp[2]=2
n=int(input())
dp=[0]*(n+1)
dp[1]=1
dp[2]=2
for i in range(3,n+1):
    dp[i]=dp[i-1]+dp[i-2]
print(dp[n])

二维dp

N=int(input())
a=[[0]*(N+1)]

# 下标从1开始
dp=[[0]*(N+1) for _ in range(N+1)]
print(dp)

for i in range(N):
    a.append([0]+list(map(int,input().split())))
print(a)
#dp[i][j]表示从(i,j)出发到底部的最大和
#最终答案=dp[1][1]
#(i,j)可以走到(i+1,j)或者(i+1,j+1)
#dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+a[i][j]

for i in range(N,0,-1):
    for j in range(1,i+1):
        # 表示是最后一行
        if i==N:
            dp[i][j]=a[i][j]
        else:
            dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+a[i][j]
print(dp[1][1])

最长上升子序列

#dp[i] 表示第i个数字结尾的最长上升子序列长度
#dp[i]可以从dp[i]...dp[i-1]转移过来，前提是a[j]<a[i]
#dp[i]=Max(dp[j]+1),j<i and a[j]<a[i]
n=int(input())
a=[0]+list(map(int,input().split()))

dp=[0]*(n+1)

for i in range(1,n+1):
    dp[i]=1 #至少包含自己
    #在位置i之前找到数字小于a[i]的数字a[j]
    for j in range(1,i):
        if a[j]<a[i]:
            dp[i]=max(dp[i],dp[j]+1)
print(max(dp))

最长公共子序列

n,m=map(int,input().split())
#下标从1开始
a=[0]+list(map(int,input().split()))
b=[0]+list(map(int,input().split()))
dp=[[0]*(m+1) for _ in range(n+1)]

#dp[i][j]=dp[i-1][j-1]  if a[i]=b[j]
#dp[i][j]=max(dp[i-1][j],dp[i][j-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])

v#ans表示最长公共子序列
ans=[]
x,y=n,m
while x!=0 and y!=0:
    if dp[x][y]==dp[x-1][y]:
        x-=1
    elif dp[x][y]==dp[x][y-1]:
        y-=1
    else:
        #此时a[x]==b[y]
        ans.append(a[x])
        x-=1
        y-=1
#反向输出
print(ans[::-1])