蓝桥杯 第四十八天 线性DP && 背包回顾_dp = [1 for i in range(n)] for j in range(m)

目录

1.187. 导弹防御系统 - AcWing题库

2.最长公共子序列

3.最长上升子序列

4.272. 最长公共上升子序列 - AcWing题库

5.01背包

（1）最初解法

6.983. 最低票价 - 力扣（LeetCode） (leetcode-cn.com)

---

1.187. 导弹防御系统 - AcWing题库

def dfs(num,l,d):
    global ans
    if l+d>=ans:
        return
    if num==n:
        ans=l+d
        return
    k=0
    while k<l and up[k]>=a[num]:
        k+=1
    temp=up[k]
    up[k]=a[num]
    if k<l:
        dfs(num+1,l,d)
    else:
        dfs(num+1,l+1,d)
    up[k]=temp
    k=0
    while k<d and down[k]<=a[num]:
        k+=1
    temp=down[k]
    down[k]=a[num]
    if k<d:
        dfs(num+1,l,d)
    else:
        dfs(num+1,l,d+1)
    down[k]=temp
 
while True:
    n=int(input())
    if n==0:
        break
    a=list(map(int,input().split()))
    up=[0 for i in range(n)]
    down=[0 for i in range(n)]
    ans=n
    dfs(0,0,0)
    print(ans)

2.最长公共子序列

n=int(input())
a=list(map(int,input().split()))
b=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]=max(dp[i-1][j],dp[i][j-1])
        if a[i-1]==b[j-1]:
            dp[i][j]=dp[i-1][j-1]+1
print(dp[-1][-1])

3.最长上升子序列

n=int(input())
a=[-1<<31]+list(map(int,input().split()))
dp=[0 for i in range(n+1)]
for i in range(1,n+1):
    for j in range(i):
        if a[i]>=a[j]:
            dp[i]=max(dp[i],dp[j]+1)
print(dp[-1])

4.272. 最长公共上升子序列 - AcWing题库

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
    for j in range(1,n+1):
        dp[i][j]=dp[i-1][j]
        if a[i]==b[j]:
            dp[i][j]=max(dp[i][j],maxv)
        if b[j]<a[i]:
            maxv=max(maxv,dp[i][j]+1)
            # for k in range(1,j):
            #     if b[k]<a[i]:
            #         dp[i][j]=max(dp[i][j],dp[i-1][k]+1)
        # else:
        #     dp[i][j]=dp[i-1][j]
for i in dp:
    print(i)
print(max(dp[-1]))

5.01背包

昨晚的模拟赛，今晚的最长公共上升子序列让我发现我的dp有很大的问题，回去复习01背包，果然发现问题很大

（1）最初解法

dp永远都是状态的继承，01背包问题，在当前的决策上，有两种

第一种，我不要第i个物品，代码如下，这是无论如何都要继承的

无论如何的意思是，不管当年这个物品的体积能否放得下， 这个物品的价值如何，我们都有可能从这个状态转移来，所以记住这个无论如何

dp[i][j]=dp[i-1][j]

第二种，要第i个物品，这时候就不能无论如何了，因为你得考虑当前背包的容量能否容纳这个物品。如果这个背包可以容纳，那么就可以尝试更新一下，这里的max函数其实比较的第二种和第一种状态继承时的大小

if j>=vs[i]:
            dp[i][j]=max(dp[i][j],dp[i-1][j-vs[i]]+w[i])

最终代码

n,v=map(int,input().split())
dp=[[0 for i in range(v+1)]for j in range(n+1)]
vs,w=[0],[0]
for i in range(n):
    vi,wi=map(int,input().split())
    vs.append(vi)
    w.append(wi)
for i in range(1,n+1):
    for j in range(1,v+1):
        dp[i][j]=dp[i-1][j]
        if j>=vs[i]:
            dp[i][j]=max(dp[i][j],dp[i-1][j-vs[i]]+w[i])
print(dp[-1][-1])

6.983. 最低票价 - 力扣（LeetCode） (leetcode-cn.com)

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        dp=[0 for i in range(max(days)+1)]
        for i in range(1,max(days)+1):
            if i not in days:
                dp[i]=dp[i-1]
            else:
                x1=max(i-1,0)
                x2=max(i-7,0)
                x3=max(i-30,0)
                dp[i]=min(dp[x1]+costs[0],dp[x2]+costs[1],dp[x3]+costs[2])
        return dp[-1]